Finding skew partitions efficiently

DOI10.1007/10719839_18MaRDI QIDQ4508373zbMATH OpenFDO

Authors Sulamita Klein, Yoshiharu Kohayakawa, Celina M. H. de Figueiredo, Bruce Reed

Publication date 14 May 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/10719839_18

zbMATH Keywords

polynomial-time algorithmskew partitionstrong perfect graph conjecture

Mathematics Subject Classification ID

Perfect graphs (05C17) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1545651
• Fast Skew Partition Recognition
• Stable skew partition problem
• List Partitions
• Complexity of graph partition problems

Cited in

(13)

• Bipartite graphs without a skew star
• Stable skew partition problem
• The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
• Decomposing Berge graphs and detecting balanced skew partitions
• Skew partition sandwich problem is NP-complete
• Colouring perfect graphs with bounded clique number
• scientific article; zbMATH DE number 1545651 (Why is no real title available?)
• FindingH-partitions efficiently
• Fast Skew Partition Recognition
• The external constraint 4 nonempty part sandwich problem
• The list partition problem for graphs
• The polynomial dichotomy for three nonempty part sandwich problems
• The polynomial dichotomy for three nonempty part sandwich problems

This page was built for publication: Finding skew partitions efficiently

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