The graph sandwich problem for 1-join composition is NP-complete
From MaRDI portal
Publication:1613390
DOI10.1016/S0166-218X(01)00246-3zbMath0995.05133WikidataQ59904349 ScholiaQ59904349MaRDI QIDQ1613390
Sulamita Klein, Kristina Vušković, Celina M. Herrera de Figueiredo
Publication date: 29 August 2002
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
computational complexitygraph algorithmperfect graphsplit decompositionsandwich problemjoin decomposition
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17)
Related Items (15)
Can transitive orientation make sandwich problems easier? ⋮ On decision and optimization (\(k\),\(l\))-graph sandwich problems ⋮ The pair completion algorithm for the homogeneous set sandwich problem ⋮ The polynomial dichotomy for three nonempty part sandwich problems ⋮ The polynomial dichotomy for three nonempty part sandwich problems ⋮ Complexity issues for the sandwich homogeneous set problem ⋮ The external constraint 4 nonempty part sandwich problem ⋮ 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 ⋮ The sandwich problem for cutsets: clique cutset, \(k\)-star cutset ⋮ On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs ⋮ The sandwich problem for decompositions and almost monotone properties ⋮ The graph sandwich problem for \(P_4\)-sparse graphs ⋮ Unnamed Item ⋮ The P4-sparse Graph Sandwich Problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The homogeneous set sandwich problem
- A semi-strong perfect graph theorem
- \(P_ 4\)-trees and substitution decomposition
- Complexity and algorithms for graph and hypergraph sandwich problems
- Bounded degree interval sandwich problems
- Matrix sandwich problems
- On the complexity of DNA physical mapping
- Normal hypergraphs and the perfect graph conjecture
- Incremental modular decomposition
- A Combinatorial Decomposition Theory
- Decomposition of Directed Graphs
- Complexity and algorithms for reasoning about time
- Graph Sandwich Problems
- Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
- The NP-completeness column: An ongoing guide
This page was built for publication: The graph sandwich problem for 1-join composition is NP-complete