Results 71 to 80 of about 3,161 (171)
On tree decompositions whose trees are minors
Journal of Graph Theory, Volume 106, Issue 2, Page 296-306, June 2024.Abstract In 2019, Dvořák asked whether every connected graph G $G$ has a tree decomposition ( T , B ) $(T,{\rm{ {\mathcal B} }})$ so that T $T$ is a subgraph of G $G$ and the width of ( T , B ) $(T,{\rm{ {\mathcal B} }})$ is bounded by a function of the treewidth of G $G$.
Pablo Blanco +5 more
wiley +1 more source
A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank [PDF]
, 2017 For even $k$, the matchings connectivity matrix $\mathbf{M}_k$ encodes which pairs of perfect matchings on $k$ vertices form a single cycle. Cygan et al.
Curticapean, Radu +2 more
core +3 more sources
The product structure of squaregraphs
Journal of Graph Theory, Volume 105, Issue 2, Page 179-191, February 2024.Abstract A squaregraph is a plane graph in which each internal face is a 4‐cycle and each internal vertex has degree at least 4. This paper proves that every squaregraph is isomorphic to a subgraph of the semistrong product of an outerplanar graph and a path.
Robert Hickingbotham +3 more
wiley +1 more source
Exclusive graph searching vs. pathwidth
Information and Computation, 2017 In Graph Searching, a team of searchers aims at capturing an invisible fugitive moving arbitrarily fast in a graph. Equivalently, the searchers try to clear a contaminated network. The problem is to compute the minimum number of searchers required to accomplish this task.
Markou, Euripides +2 more
openaire +2 more sources
IET Intelligent Transport Systems, Volume 18, Issue 1, Page 186-202, January 2024.In the context of automated driving, the connected and automated vehicles (CAVs) technology unlock the energy saving potential. This paper develops an LSTM‐based deep learning framework for eco‐driving adaptive identification on Intelligent vehicle multivariate time series data.
Lixin Yan +4 more
wiley +1 more source
Seymour’s Conjecture on 2-Connected Graphs of Large Pathwidth [PDF]
Combinatorica, 2020 We prove the conjecture of Seymour (1993) that for every apex-forest $H_1$ and outerplanar graph $H_2$ there is an integer $p$ such that every 2-connected graph of pathwidth at least $p$ contains $H_1$ or $H_2$ as a minor. An independent proof was recently obtained by Dang and Thomas.
Huynh T., Joret G., Micek P., Wood D. R.
openaire +4 more sources
A 3-approximation for the pathwidth of Halin graphs
Journal of Discrete Algorithms, 2004 AbstractWe prove that the pathwidth of Halin graphs can be 3-approximated in linear time. Our approximation algorithms is based on a combinatorial result about respectful edge orderings of trees. Using this result we prove that the linear width of Halin graph is always at most three times the linear width of its skeleton.
Dimitrios M. Thilikos, Fedor V. Fomin
openaire +3 more sources
The Effect of Planarization on Width
, 2017 We study the effects of planarization (the construction of a planar diagram $D$ from a non-planar graph $G$ by replacing each crossing by a new vertex) on graph width parameters.
DG Corneil +14 more
core +1 more source
On the Geometric Ramsey Number of Outerplanar Graphs
, 2013 We prove polynomial upper bounds of geometric Ramsey numbers of pathwidth-2 outerplanar triangulations in both convex and general cases. We also prove that the geometric Ramsey numbers of the ladder graph on $2n$ vertices are bounded by $O(n^{3})$ and $O(
Cibulka, Josef +4 more
core +1 more source
The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations
AlgorithmsTree-width and path-width are well-known graph parameters. Many NP-hard graph problems admit polynomial-time solutions when restricted to graphs of bounded tree-width or bounded path-width. In this work, we study the behavior of tree-width and path-width
Frank Gurski, Robin Weishaupt
doaj +1 more source