On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
From MaRDI portal
Publication:995559
DOI10.1016/j.tcs.2007.04.007zbMath1188.68211OpenAlexW2049564405MaRDI QIDQ995559
R. Sritharan, Luérbio Faria, Celina M. Herrera de Figueiredo, Sulamita Klein
Publication date: 3 September 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2007.04.007
Related Items
Bipartite completion of colored graphs avoiding chordless cycles of given lengths ⋮ Graph modification problem for some classes of graphs ⋮ Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone ⋮ Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs ⋮ Chordal bipartite completion of colored graphs ⋮ On the forbidden induced subgraph sandwich problem ⋮ The chain graph sandwich problem ⋮ Strongly chordal and chordal bipartite graphs are sandwich monotone ⋮ The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory ⋮ Some completion problems for graphs without chordless cycles of prescribed lengths ⋮ Completing colored graphs to meet a target property ⋮ The graph sandwich problem for \(P_4\)-sparse graphs ⋮ On the Complexity of Probe and Sandwich Problems for Generalized Threshold Graphs ⋮ Partitions and well-coveredness: the graph sandwich problem
Cites Work
- Unnamed Item
- Unnamed Item
- The homogeneous set sandwich problem
- Which claw-free graphs are perfectly orderable?
- Weakly triangulated graphs
- On the complexity of recognizing perfectly orderable graphs
- Characterizations of strongly chordal graphs
- Classes of bipartite graphs related to chordal graphs
- Some simplified NP-complete graph problems
- Complexity and algorithms for graph and hypergraph sandwich problems
- Bounded degree interval sandwich problems
- Matrix sandwich problems
- The graph sandwich problem for 1-join composition is NP-complete
- On decision and optimization (\(k\),\(l\))-graph sandwich problems
- Chordal bipartite completion of colored graphs
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Characterizations of totally balanced matrices
- Totally-Balanced and Greedy Matrices
- Doubly Lexical Orderings of Matrices
- Algorithmic Aspects of Vertex Elimination on Graphs
- Graph Classes: A Survey
- Graph Sandwich Problems
- Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
- Two strikes against perfect phylogeny
This page was built for publication: On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
