Results 1 to 10 of about 2,027 (101)
Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
, 2018 Deciding whether a given graph has a square root is a classical problem that has been studied extensively both from graph theoretic and from algorithmic perspectives.
A Mukhopadhyay +24 more
core +1 more source
SIAM Journal on Discrete MathematicsThe {\em circumference} of a graph $G$ with at least one cycle is the length of a longest cycle in $G$. A classic result of Birmelé (2003) states that the treewidth of $G$ is at most its circumference minus $1$. In case $G$ is $2$-connected, this upper bound also holds for the pathwidth of $G$; in fact, even the treedepth of $G$ is upper bounded by its
Marcin Briański +2 more
openaire +2 more sources
On the pathwidth of chordal graphs
Discrete Applied Mathematics, 1993 special issue for ARIDAM IV ...
openaire +3 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
On the Pathwidth of Planar Graphs [PDF]
, 2006 Fomin and Thilikos in [5] conjectured that there is a constant $c$ such that, for every $2$-connected planar graph $G$, {pw}(G^*) \leq 2\text{pw}(G)+c$ (the same question was asked simutaneously by Coudert, Huc and Sereni in [4]). By the results of Boedlander and Fomin [2] this holds for every outerplanar graph and actually is tight by Coudert, Huc and
Amini, Omid +2 more
openaire +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
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
Partitions and Coverings of Trees by Bounded-Degree Subtrees [PDF]
, 2010 This paper addresses the following questions for a given tree $T$ and integer $d\geq2$: (1) What is the minimum number of degree-$d$ subtrees that partition $E(T)$? (2) What is the minimum number of degree-$d$ subtrees that cover $E(T)$?
Wood, David R.
core
The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs
, 2014 We study the problem of transforming one list (vertex) coloring of a graph into another list coloring by changing only one vertex color assignment at a time, while at all times maintaining a list coloring, given a list of allowed colors for each vertex ...
Hatanaka, Tatsuhiko +2 more
core +1 more source
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 ...
Dalmau, V., Krokhin, A.
openaire +3 more sources