The graph sandwich problem for \(P_4\)-sparse graphs

DOI10.1016/j.disc.2008.01.014zbMath1200.05222OpenAlexW2073656342MaRDI QIDQ1025565

Simone Dantas, Aurora Morgana, Célia Picinin de Mello, Sulamita Klein

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Related Items (5)

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

Cites Work

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

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