The polynomial dichotomy for three nonempty part sandwich problems

DOI10.1016/J.DAM.2009.12.002zbMath1209.05191OpenAlexW2027335394MaRDI QIDQ5901068

Rafael B. Teixeira, Celina M. Herrera de Figueiredo, Simone Dantas

Publication date: 13 August 2010

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

Full work available at URL: https://doi.org/10.1016/j.dam.2009.12.002

zbMATH Keywords

computational complexitygraph algorithmsNP-completesandwich problemsgraph partitionsstructural characterization of graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

On the forbidden induced subgraph sandwich problem ⋮ The chain graph 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 ⋮ Sandwiches missing two ingredients of order four

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The homogeneous set sandwich problem
• The strong perfect graph theorem
• Star-cutsets and perfect graphs
• On stable cutsets in graphs
• The graph sandwich problem for 1-join composition is NP-complete
• Stable skew partition problem
• On decision and optimization (\(k\),\(l\))-graph sandwich problems
• Extended skew partition problem
• The sandwich problem for cutsets: clique cutset, \(k\)-star cutset
• List Partitions
• FindingH-partitions efficiently
• Graph Sandwich Problems

This page was built for publication: The polynomial dichotomy for three nonempty part sandwich problems