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

chordal bipartite graphstreewidth

Mathematics Subject Classification ID

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

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

(21)

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