Treewidth of Chordal Bipartite Graphs

DOI10.1006/JAGM.1995.1037MaRDI QIDQ4845852zbMATH OpenOpenAlexFDO

Authors Ton Kloks, Dieter Kratsch

Publication date 28 May 1996

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://dspace.library.uu.nl/handle/1874/16671

zbMATH Keywords

treewidthchordal bipartite graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Recommendations

• scientific article; zbMATH DE number 512817
• Chordal bipartite graphs of bounded tree- and clique-width
• Treewidth for graphs with small chordality
• Exact Algorithms for Treewidth and Minimum Fill-In
• Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph

Cited in

(19)

• Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
• On 3-degree 4-chordal graphs
• \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
• Chordal embeddings of planar graphs
• A revisit of the scheme for computing treewidth and minimum fill-in
• Listing all potential maximal cliques of a graph
• On list \(k\)-coloring convex bipartite graphs
• Treewidth for graphs with small chordality
• On factorial properties of chordal bipartite graphs
• On the Treewidth and Pathwidth of Biconvex Bipartite Graphs
• Connected graph searching in chordal graphs
• A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
• Partially ordered knapsack and applications to scheduling
• Chordal bipartite graphs of bounded tree- and clique-width
• Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
• The treewidth of 2-section of hypergraphs
• Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
• Transversals of longest cycles in chordal and bounded tree-width graphs
• Approximation hardness of domination problems on generalized convex graphs

This page was built for publication: Treewidth of Chordal Bipartite Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4845852)