The graph sandwich problem for \(P_4\)-sparse graphs
From MaRDI portal
Publication:1025565
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
algorithmscomputational complexitycographspartition problemsgraph sandwich problems\(P_{4}\)-sparse graphs
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
- P4-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
