𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Treewidth of Chordal Bipartite Graphs

✍ Scribed by T. Kloks; D. Kratsch

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
743 KB
Volume
19
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

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. We present a polynomial time algorithm for the exact computation of the treewidth of all chordal bipartite graphs. The algorithm can be implemented to run in time (O\left(m^{\alpha}\right)) which is the time needed to multiply two (m \times m) matrices, where (m) is the number of edges of the graph. (1995 Academic Press, Inc.

πŸ“œ SIMILAR VOLUMES

Perfect Elimination and Chordal Bipartit
Perfect Elimination and Chordal Bipartite Graphs
✍ Martin Charles Golumbic; Clinton F. Goss πŸ“‚ Article πŸ“… 1978 πŸ› John Wiley and Sons 🌐 English βš– 348 KB

## Abstract We define two types of bipartite graphs, chordal bipartite graphs and perfect elimination bipartite graphs, and prove theorems analogous to those of Dirac and Rose for chordal graphs (rigid circuit graphs, triangulated graphs). Our results are applicable to Gaussian elimination on spars

Hamiltonian circuits in chordal bipartit
Hamiltonian circuits in chordal bipartite graphs
✍ Haiko MΓΌller πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 359 KB

The main result of this paper is the NP-completeness of the HAMILTONIAN CIRCUIT problem for chordal bipartite graphs. This is proved by a sophisticated reduction from SATISFIABILITY. As a corollary, HAMILTONIAN CIRCUIT is NP-complete for strongly chordal split graphs. On both classes the complexity

On bounded treewidth duality of graphs
On bounded treewidth duality of graphs
✍ Ne?et?il, Jaroslav; Zhu, Xuding πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 734 KB

For a graph H , the H-coloring problem is to decide whether or not an instance graph G is homomorphic to H . The H-coloring problem is said to have bounded treewidth duality if there is an integer k such that for any graph G which is not homomorphic to H , there is a graph F of treewidth k which is

A generalization of chordal graphs
A generalization of chordal graphs
✍ P. D. Seymour; R. W. Weaver πŸ“‚ Article πŸ“… 1984 πŸ› John Wiley and Sons 🌐 English βš– 487 KB

In a 3-connected planar triangulation, every circuit of length 2 4 divides the rest of the edges into two nontrivial parts (inside and outside) which are "separated" by the circuit. Neil Robertson asked to what extent triangulations are characterized by this property, and conjectured an answer. In t

Vertex partitions of chordal graphs
Vertex partitions of chordal graphs
✍ David R. Wood πŸ“‚ Article πŸ“… 2006 πŸ› John Wiley and Sons 🌐 English βš– 103 KB

## Abstract A __k‐tree__ is a chordal graph with no (__k__ + 2)‐clique. An ℓ‐__tree‐partition__ of a graph __G__ is a vertex partition of __G__ into β€˜bags,’ such that contracting each bag to a single vertex gives an ℓ‐tree (after deleting loops and replacing parallel edges by a single edge). We pro