Strongly chordal and chordal bipartite graphs are sandwich monotone

DOI10.1007/S10878-010-9322-XMaRDI QIDQ652637zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, F. Mancini, Charis Papadopoulos, R. Sritharan

Publication date 15 December 2011

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-010-9322-x

zbMATH Keywords

chordal bipartite graphsstrongly chordal graphsminimal completionssandwich monotonicity

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Structural characterization of families of graphs (05C75)

Recommendations

• Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone
• On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
• New results on chordal-(\(k, l\)) and strongly chordal-(\(k, l\)) sandwich problems
• Graph Sandwich Problems
• Chordal bipartite completion of colored graphs

Cites work

• A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithmic graph theory and perfect graphs
• Characterizations of strongly chordal graphs
• Characterizing Minimal Interval Completions
• Characterizing and Computing Minimal Cograph Completions
• Chordal bipartite completion of colored graphs
• Complexity classification of some edge modification problems
• Computing the Minimum Fill-In is NP-Complete
• Doubly lexical ordering of dense 0--1 matrices
• Every monotone graph property is testable
• Exact Algorithms for Treewidth and Minimum Fill-In
• Measures on monotone properties of graphs
• Minimal split completions
• On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
• On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
• Safe separators for treewidth
• Several results on chordal bipartite graphs
• Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
• Three Partition Refinement Algorithms
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Treewidth and minimum fill-in: Grouping the minimal separators
• Triangulated graphs and the elimination process

Cited in

(2)

• Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone
• Graph modification problem for some classes of graphs

This page was built for publication: Strongly chordal and chordal bipartite graphs are sandwich monotone

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