Strongly chordal and chordal bipartite graphs are sandwich monotone
From MaRDI portal
Publication:652637
DOI10.1007/S10878-010-9322-XzbMATH Open1230.90161OpenAlexW1986338131MaRDI QIDQ652637FDOQ652637
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
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
- Algorithmic graph theory and perfect graphs
- Doubly lexical ordering of dense 0--1 matrices
- Three Partition Refinement Algorithms
- Characterizations of strongly chordal graphs
- Triangulated graphs and the elimination process
- Algorithmic Aspects of Vertex Elimination on Graphs
- Treewidth and minimum fill-in: Grouping the minimal separators
- Exact Algorithms for Treewidth and Minimum Fill-In
- Computing the Minimum Fill-In is NP-Complete
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Complexity classification of some edge modification problems
- Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
- Chordal bipartite completion of colored graphs
- On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
- Minimal split completions
- Safe separators for treewidth
- Every monotone graph property is testable
- A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
- Characterizing and Computing Minimal Cograph Completions
- On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
- Characterizing Minimal Interval Completions
- Several results on chordal bipartite graphs
- Measures on monotone properties of graphs
Cited In (2)
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)
