The polynomial dichotomy for three nonempty part sandwich problems

DOI10.1016/j.endm.2008.01.015zbMath1341.05240OpenAlexW2174934505MaRDI QIDQ5900084

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

Publication date: 5 June 2008

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2008.01.015

zbMATH Keywords

computational complexitygraph algorithmsstructural characterization of graphs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (2)

The external constraint 4 nonempty part sandwich problem ⋮ Skew partition sandwich problem is NP-complete

Cites Work

• Unnamed Item
• Unnamed Item
• The homogeneous set sandwich problem
• The strong perfect graph theorem
• Star-cutsets and perfect 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