The polynomial dichotomy for three nonempty part sandwich problems

DOI10.1016/J.ENDM.2008.01.015MaRDI QIDQ5900084zbMATH OpenOpenAlexFDO

Authors R. B. Teixeira, Simone Dantas, Celina M. H. de Figueiredo

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

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

Cites work

• Extended skew partition problem
• FindingH-partitions efficiently
• Graph Sandwich Problems
• scientific article; zbMATH DE number 1512686 (Why is no real title available?)
• List Partitions
• On decision and optimization (\(k\),\(l\))-graph sandwich problems
• Stable skew partition problem
• Star-cutsets and perfect graphs
• The graph sandwich problem for 1-join composition is NP-complete
• The homogeneous set sandwich problem
• The list partition problem for graphs
• The sandwich problem for cutsets: clique cutset, \(k\)-star cutset
• The strong perfect graph theorem

Cited in

(3)

• Skew partition sandwich problem is NP-complete
• The external constraint 4 nonempty part sandwich problem
• Rectangular partition is polynomial in two dimensions but NP-complete in three

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5900084)