Results 1 to 10 of about 1,502 (163)

Treewidth of Circular-Arc Graphs

SIAM Journal on Discrete Mathematics, 1994
It is shown that the treewidth of circular-arc graphs and the corresponding tree-decomposition can be found in \(O(n^ 3)\) time. Let \(G= (V,E)\) be a circular-arc graph corresponding to a family \(\{A_ 0, A_ 1,\dots, A_{n-1}\}\) of arcs on a unit circle. Define a left clique \(S_ i\) by \(S_ i= \{A_ j\mid A_ j\) contains the left end points of \(A_ i\}
C. Pandu Rangan, Ravi Sundaram, Karan Singh   +2 more
openaire   +3 more sources

Treewidth: Structure and Algorithms

2007
This paper surveys some aspects of the graph theoretic notion of treewidth. In particular, we look at the interaction between different characterizations of the notion, and algorithms and algorithmic applications.
openaire   +3 more sources

Introduction to Treewidth

2018
Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi, Fedor V. Fomin   +3 more
openaire   +2 more sources

Heuristics for Treewidth [PDF]

, 2013
Michael R. Fellows, Rodney G. Downey
openaire   +1 more source

Treewidth: Computational Experiments [PDF]

Electronic Notes in Discrete Mathematics, 2001
Many {\cal NP}-hard graph problems can be solved in polynomial time for graphs with bounded treewidth. Equivalent results are known for pathwidth and branchwidth. In recent years, several studies have shown that this result is not only of theoretical interest but can successfully be applied to find (almost) optimal solutions or lower bounds for diverse
Arie M. C. A. Koster, Hans L. Bodlaender, Stan P.M. van Hoesel   +2 more
openalex   +12 more sources

Girth and treewidth

Journal of Combinatorial Theory, Series B, 2005
Graphs of high girth have been much studied, especially in the context of the minimum vertex number of graphs of given girth and minimum degree. The authors study the treewidth \(\text{tw}(G)\) of a graph \(G\), giving a lower bound in terms of the girth \(g(G)\) and average degree \(d(G)\). They show that \[ \text{tw}(G)\geq c {1\over g(G)+1} (d(G)-1)^
L. Sunil Chandran, C. R. Subramanian
openalex   +4 more sources

Boxicity and Treewidth

Journal of Combinatorial Theory, Series B, 2005
25 ...
L. Sunil Chandran, Naveen Sivadasan
openalex   +5 more sources

Treewidth of Chordal Bipartite Graphs [PDF]

Journal of Algorithms, 1995
Summary: Chordal bipartite graphs are exactly those bipartite graphs in which every cycle of length at least six has a chord. The treewidth of a graph \(G\) is the smallest maximum cliquesize among all chordal supergraphs of \(G\) decreased by one.
Ton Kloks, Dieter Kratsch
openalex   +8 more sources

Computing Treewidth on the GPU

arXiv, 2017
We present a parallel algorithm for computing the treewidth of a graph on a GPU. We implement this algorithm in OpenCL, and experimentally evaluate its performance. Our algorithm is based on an $O^*(2^{n})$-time algorithm that explores the elimination orderings of the graph using a Held-Karp like dynamic programming approach.
Tom C. van der Zanden, Hans L. Bodlaender   +1 more
openalex   +8 more sources

On the treewidths of graphs of bounded degree. [PDF]

PLoS One, 2015
In this paper, we develop a new technique to study the treewidth of graphs with bounded degree. We show that the treewidth of a graph G = (V, E) with maximum vertex degree d is at most [Formula: see text] for sufficiently large d, where C is a constant.
Song Y, Yu M.
europepmc   +6 more sources