Results 21 to 30 of about 609 (128)
Approximating Pathwidth for Graphs of Small Treewidth [PDF]
ACM Transactions on Algorithms, 2022 We describe a polynomial-time algorithm which, given a graphGwith treewidtht, approximates the pathwidth ofGto within a ratio of\(O(t\sqrt {\log t})\). This is the first algorithm to achieve anf(t)-approximation for some functionf.Our approach builds on the following key insight: every graph with large pathwidth has large treewidth or contains a ...
Carla Groenland +3 more
openalex +8 more sources
The treewidth and pathwidth of graph unions
SIAM Journal on Discrete Mathematics, 2022 Given two $n$-vertex graphs $G_1$ and $G_2$ of bounded treewidth, is there an $n$-vertex graph $G$ of bounded treewidth having subgraphs isomorphic to $G_1$ and $G_2$? Our main result is a negative answer to this question, in a strong sense: we show that the answer is no even if $G_1$ is a binary tree and $G_2$ is a ternary tree.
Bogdan Alecu +5 more
openalex +4 more sources
The structure of obstructions to treewidth and pathwidth
Electronic Notes in Discrete Mathematics, 2002 AbstractIt is known that the class of graphs with treewidth (resp. pathwidth) bounded by a constant w can be characterized by a finite obstruction set obs(TW(w)) (resp. obs(PW(w))). These obstruction sets are known for w⩽3 so far. In this paper we give a structural characterization of graphs from obs(TW(w)) (resp.
Janka Chlebı́ková
openalex +5 more sources
Majority constraints have bounded pathwidth duality [PDF]
European Journal of Combinatorics, 2008 We study certain constraint satisfaction problems which are the problems of deciding whether there exists a homomorphism from a given relational structure to a fixed structure with a majority polymorphism. We show that such a problem is equivalent to deciding whether the given structure admits a homomorphism from an obstruction belonging to a certain ...
Víctor Dalmau, Andrei Krokhin
openalex +4 more sources
On Exploring Temporal Graphs of Small Pathwidth [PDF]
arXiv, 2018 We show that the Temporal Graph Exploration Problem is NP-complete, even when the underlying graph has pathwidth 2 and at each time step, the current graph is connected.
Bodlaender, Hans L. +1 more
arxiv +6 more sources
Tree-decompositions of small pathwidth
Electronic Notes in Discrete Mathematics, 2004 AbstractMotivated by the desire to speed up dynamic programming algorithms for graphs of bounded treewidth, we initiate a study of the tradeoff between width and pathwidth of tree-decompositions. We therefore investigate the catwidth parameter catw(G) which is the minimum width of any tree-decomposition (T,X) of a graph G when the pathwidth pw(T) of ...
Jan Arne Telle
openalex +4 more sources
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
Separating layered treewidth and row treewidth [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 Layered treewidth and row treewidth are recently introduced graph parameters that have been key ingredients in the solution of several well-known open problems.
Prosenjit Bose +4 more
doaj +1 more source
New Algorithms for Mixed Dominating Set [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 A mixed dominating set is a collection of vertices and edges that dominates all vertices and edges of a graph. We study the complexity of exact and parameterized algorithms for \textsc{Mixed Dominating Set}, resolving some open questions.
Louis Dublois +2 more
doaj +1 more source