Results 21 to 30 of about 2,730 (147)
SIAM Journal on Discrete Mathematics, 2023 The {\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
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
On the pathwidth of hyperbolic 3-manifolds [PDF]
, 2021 Selon le célèbre théorème de rigidité de Mostow, la géométrie des 3-variétés hyperboliques fermées est entièrement déterminée par leur topologie. En particulier, le volume de ces variétés est un invariant topologique et, en tant que tel, a été étudié pendant un demi-siècle.
Kristóf Huszár
openalex +5 more sources
Approximation of pathwidth of outerplanar graphs [PDF]
Journal of Algorithms, 2002 There exists a polynomial time algorithm to compute the pathwidth of outerplanar graphs, but the large exponent makes this algorithm impractical. In this paper, we give an algorithm that, given a biconnected outerplanar graph G, finds a path decomposition of G of pathwidth at most twice the pathwidth of G plus one.
Hans L. Bodlaender, Fedor V. Fomin
openalex +9 more sources
The pathwidth and treewidth of cographs [PDF]
SIAM Journal on Discrete Mathematics, 1990 It is shown that the pathwidth of a cograph equals its treewidth, and a linear time algorithm to determine the pathwidth of a cograph and build a corresponding path-decomposition is given.
Hans L. Bodlaender, Rolf H. Möhring
openalex +4 more sources
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
Pathwidth, trees, and random embeddings [PDF]
Combinatorica, 2009 We prove that, for every $k=1,2,...,$ every shortest-path metric on a graph of pathwidth $k$ embeds into a distribution over random trees with distortion at most $c$ for some $c=c(k)$. A well-known conjecture of Gupta, Newman, Rabinovich, and Sinclair states that for every minor-closed family of graphs $F$, there is a constant $c(F)$ such that the ...
James R. Lee, Anastasios Sidiropoulos
openalex +4 more sources
A new two-variable generalization of the chromatic polynomial [PDF]
Discrete Mathematics & Theoretical Computer Science, 2003 We present a two-variable polynomial, which simultaneously generalizes the chromatic polynomial, the independence polynomial, and the matching polynomial of a graph.
Klaus Dohmen +2 more
doaj +3 more sources
Classes of graphs with restricted interval models [PDF]
Discrete Mathematics & Theoretical Computer Science, 1999 We introduce q-proper interval graphs as interval graphs with interval models in which no interval is properly contained in more than q other intervals, and also provide a forbidden induced subgraph characterization of this class of graphs. We initiate a
Andrzej Proskurowski, Jan Arne Telle
doaj +3 more sources
Recent Advances in Positive-Instance Driven Graph Searching
Algorithms, 2022 Research on the similarity of a graph to being a tree—called the treewidth of the graph—has seen an enormous rise within the last decade, but a practically fast algorithm for this task has been discovered only recently by Tamaki (ESA 2017).
Max Bannach, Sebastian Berndt
doaj +1 more source