Results 51 to 60 of about 2,549 (154)
A simple linear-time algorithm for finding path-decompositions of small width [PDF]
, 1994 We described a simple algorithm running in linear time for each fixed constant $k$, that either establishes that the pathwidth of a graph $G$ is greater than $k$, or finds a path-decomposition of $G$ of width at most $O(2^{k})$.
Cattell, Kevin +2 more
core
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
On the Pathwidth of Hyperbolic 3-Manifolds
, 2021 Computing in Geometry and Topology, Vol. 1 No. 1 (2022)
openaire +4 more sources
LTL Fragments are Hard for Standard Parameterisations
, 2015 We classify the complexity of the LTL satisfiability and model checking problems for several standard parameterisations. The investigated parameters are temporal depth, number of propositional variables and formula treewidth, resp., pathwidth.
Lück, Martin, Meier, Arne
core +1 more source
A General Reduction Theorem with Applications to Pathwidth and the Complexity of MAX 2-CSP [PDF]
, 2015 We prove a general reduction theorem which allows us to extend bounds for certain graph parameters on cubic graphs to bounds for general graphs taking into account the individual vertex degrees.
A Golovnev +18 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
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
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
Structural parameterizations for boxicity [PDF]
, 2014 The boxicity of a graph $G$ is the least integer $d$ such that $G$ has an intersection model of axis-aligned $d$-dimensional boxes. Boxicity, the problem of deciding whether a given graph $G$ has boxicity at most $d$, is NP-complete for every fixed $d ...
A Adiga +19 more
core +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