✦ LIBER ✦

Strongly chordal and chordal bipartite graphs are

✍ Scribed by Pinar Heggernes; Federico Mancini; Charis Papadopoulos; R. Sritharan

Publisher: Springer US
Year: 2010
Tongue: English
Weight: 634 KB
Volume: 22
Category: Article
ISSN: 1382-6905
DOI: 10.1007/s10878-010-9322-x

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Erratum to “Chordal bipartite, strongly

Erratum to “Chordal bipartite, strongly chordal, and strongly chordal bipartite graphs”: [Discrete Mathematics 260 (2003) 231–238]

✍ Terry A. McKee 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 70 KB

Chordal bipartite graphs and crowns

✍ Vincent Bouchitté 📂 Article 📅 1985 🏛 Springer Netherlands 🌐 English ⚖ 178 KB

Treewidth of Chordal Bipartite Graphs

✍ T. Kloks; D. Kratsch 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 743 KB

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 computa

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

Matching and multidimensional matching i

Matching and multidimensional matching in chordal and strongly chordal graphs

✍ Elias Dahlhaus; Marek Karpinski 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 877 KB

Chordal graphs are graphs with the property that each cycle of length greater than 3 has two non-consecutive vertices that are joined by an edge. An important subclass of chordal graphs are strongly chordal graphs (Farber, 1983). Chordal graphs appear for example in the design of acyclic data base s

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