The graph sandwich problem for P₄-sparse graphs

DOI10.1016/J.DISC.2008.01.014zbMATH Open1200.05222OpenAlexW2073656342MaRDI QIDQ1025565FDOQ1025565

Authors: Simone Dantas, Aurora Morgana, Sulamita Klein, Célia P. de Mello 

Publication date: 19 June 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2008.01.014

Recommendations

• Sandwiches missing two ingredients of order four
• Graph Sandwich Problems
• scientific article; zbMATH DE number 6423755
• The homogeneous set sandwich problem
• Linear time optimization algorithms for \(P_ 4\)-sparse graphs

zbMATH Keywords

algorithmscomputational complexitycographspartition problemsgraph sandwich problems\(P_{4}\)-sparse graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Title not available (Why is that?)
• Bounded degree interval sandwich problems
• Title not available (Why is that?)
• Graph Classes: A Survey
• Graph Sandwich Problems
• Depth-First Search and Linear Graph Algorithms
• Complement reducible graphs
• Modular decomposition and transitive orientation
• A tree representation for \(P_ 4\)-sparse graphs
• The homogeneous set sandwich problem
• A Linear Recognition Algorithm for Cographs
• Computing the Minimum Fill-In is NP-Complete
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• Chordal bipartite completion of colored graphs
• On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• 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
• The sandwich problem for cutsets: clique cutset, \(k\)-star cutset
• A linear-time recognition algorithm for \(P_{4}\)-reducible graphs

Cited In (6)

• The graph sandwich problem for 1-join composition is NP-complete
• Complexity issues for the sandwich homogeneous set problem
• The chain graph sandwich problem
• Sandwiches missing two ingredients of order four
• On the forbidden induced subgraph sandwich problem
• The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy

This page was built for publication: The graph sandwich problem for \(P_4\)-sparse graphs

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