The graph sandwich problem for 1-join composition is NP-complete

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)

zbMATH Keywords

computational complexitygraph algorithmperfect graphsplit decompositionsandwich problemjoin decomposition

Mathematics Subject Classification ID

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