Results 61 to 70 of about 2,730 (147)
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 AbstractIn this paper we first show that the pathwidth problem for chordal graphs is NP-hard.Then we give polynomial algorithms for subclasses. One of those classes are the k-starlike graphs – a generalization of split graphs. The other class are the primitive starlike graphs – a class of graphs where the intersection behavior of maximal cliques is ...
openaire +2 more sources
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
Superpatterns and Universal Point Sets [PDF]
, 2013 An old open problem in graph drawing asks for the size of a universal point set, a set of points that can be used as vertices for straight-line drawings of all n-vertex planar graphs.
A. Marcus +14 more
core +3 more sources
Induced subgraphs and path decompositions [PDF]
arXiv, 2022 A graph $H$ is an induced subgraph of a graph $G$ if a graph isomorphic to $H$ can be obtained from $G$ by deleting vertices. Recently, there has been significant interest in understanding the unavoidable induced subgraphs for graphs of large treewidth.
arxiv
CSP duality and trees of bounded pathwidth
Theoretical Computer Science, 2010 We study non-uniform constraint satisfaction problems definable in monadic Datalog stratified by the use of non-linearity. We show how such problems can be described in terms of homomorphism dualities involving trees of bounded pathwidth and in algebraic terms. For this, we introduce a new parameter for trees that closely approximates pathwidth and can
Catarina Carvalho +2 more
openalex +4 more sources
On the complexity of embedding in graph products [PDF]
arXiv, 2023 Graph embedding, especially as a subgraph of a grid, is an old topic in VLSI design and graph drawing. In this paper, we investigate related questions concerning the complexity of embedding a graph $G$ in a host graph that is the strong product of a path $P$ with a graph $H$ that satisfies some properties, such as having small treewidth, pathwidth or ...
arxiv
An Improved Bound for First-Fit on Posets Without Two Long Incomparable Chains
, 2012 It is known that the First-Fit algorithm for partitioning a poset P into chains uses relatively few chains when P does not have two incomparable chains each of size k. In particular, if P has width w then Bosek, Krawczyk, and Szczypka (SIAM J.
Bosek B. +8 more
core +1 more source
Tournament pathwidth and topological containment
Journal of Combinatorial Theory, Series B, 2013 We prove that if a tournament has pathwidth >=4@q^2+7@q then it has @q vertices that are pairwise @q-connected. As a consequence of this and previous results, we obtain that for every set S of tournaments the following are equivalent:*there exists k such that every member of S has pathwidth at most k, *there is a digraph H such that no subdivision of H
Paul Seymour, Alexandra Fradkin
openaire +2 more sources
Track Layouts, Layered Path Decompositions, and Leveled Planarity [PDF]
Algorithmica 81 (4): 1561-1583, 2019, 2015 We investigate two types of graph layouts, track layouts and layered path decompositions, and the relations between their associated parameters track-number and layered pathwidth. We use these two types of layouts to characterize leveled planar graphs, which are the graphs with planar leveled drawings with no dummy vertices.
arxiv +1 more source