On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs

DOI10.1016/J.TCS.2007.04.007zbMATH Open1188.68211OpenAlexW2049564405MaRDI QIDQ995559FDOQ995559

Authors: R. Sritharan, Celina M. H. de Figueiredo, Luerbio Faria, 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

Recommendations

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

zbMATH Keywords

graphchordalstrongly chordalsandwich problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Bounded degree interval sandwich problems
• Title not available (Why is that?)
• Graph Classes: A Survey
• Graph Sandwich Problems
• Some simplified NP-complete graph problems
• Characterizations of strongly chordal graphs
• Characterizations of totally balanced matrices
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Weakly triangulated graphs
• The homogeneous set sandwich problem
• Totally-Balanced and Greedy Matrices
• Doubly Lexical Orderings of Matrices
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• Which claw-free graphs are perfectly orderable?
• On the complexity of recognizing perfectly orderable graphs
• Classes of bipartite graphs related to chordal graphs
• Chordal bipartite completion of colored graphs
• Two strikes against perfect phylogeny
• Complexity and algorithms for graph and hypergraph 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
• Title not available (Why is that?)

Cited In (20)

• Can transitive orientation make sandwich problems easier?
• Partitions and well-coveredness: the graph sandwich problem
• The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
• The graph sandwich problem for \(P_4\)-sparse graphs
• Chordal bipartite completion of colored graphs
• Algorithms and complexity of sandwich problems in graphs (extended abstract)
• Complexity and algorithms for graph and hypergraph sandwich problems
• The graph sandwich problem for 1-join composition is NP-complete
• The P versus NP-complete dichotomy of some challenging problems in graph theory
• On the complexity of probe and sandwich problems for generalized threshold graphs
• Completing colored graphs to meet a target property
• The chain graph sandwich problem
• Bipartite completion of colored graphs avoiding chordless cycles of given lengths
• Some completion problems for graphs without chordless cycles of prescribed lengths
• New results on chordal-(\(k, l\)) and strongly chordal-(\(k, l\)) sandwich problems
• Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone
• Graph modification problem for some classes of graphs
• On the forbidden induced subgraph sandwich problem
• Strongly chordal and chordal bipartite graphs are sandwich monotone
• Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs

This page was built for publication: On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs

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