Results 61 to 70 of about 1,033 (146)
The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs [PDF]
Electronic Proceedings in Theoretical Computer Science, 2012 For some time the discrete strategy improvement algorithm due to Jurdzinski and Voge had been considered as a candidate for solving parity games in polynomial time.
Felix Canavoi +2 more
doaj +1 more source
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
Parameterized Algorithms for Book Embedding Problems
Journal of Graph Algorithms and Applications, 2020 A $k$-page book embedding of a graph $G$ draws the vertices of $G$ on a line and the edges on $k$ half-planes (called pages) bounded by this line, such that no two edges on the same page cross. We study the problem of determining whether $G$ admits a $k$-
Sujoy Bhore +3 more
doaj +1 more source
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
CoRRWe prove two results relating the basis number of a graph $G$ to path decompositions of $G$. Our first result shows that the basis number of a graph is at most four times its pathwidth. Our second result shows that, if a graph $G$ has a path decomposition with adhesions of size at most $k$ in which the graph induced by each bag has basis number at most
Babak Miraftab +2 more
openaire +3 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
On the pathwidth of chordal graphs
Discrete Applied Mathematics, 1993 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire +2 more sources
Pathwidth of 2-Layer k-Planar Graphs
Computing in Geometry and TopologyA bipartite graph G = (X ∪ Y, E) is a 2-layer k-planar graph if it admits a drawing on the plane such that the vertices in X and Y are placed on two parallel lines respectively, edges are drawn as straight-line segments, and every edge involves at most ...
Yuto Okada
doaj +1 more source
Pole Dancing: 3D Morphs for Tree Drawings
Journal of Graph Algorithms and Applications, 2019 We study the question whether a crossing-free 3D morph between two straight-line drawings of an $n$-vertex tree $T$ can be constructed consisting of a small number of linear morphing steps. We look both at the case in which the two given drawings are two-
Elena Arseneva +7 more
doaj +1 more source
On first-order transductions of classes of graphs [PDF]
Logical Methods in Computer ScienceWe study various aspects of the first-order transduction quasi-order on graph classes, which provides a way of measuring the relative complexity of graph classes based on whether one can encode the other using a formula of first-order (FO) logic.
Samuel Braunfeld +3 more
doaj +1 more source