Extended skew partition problem

DOI10.1016/J.DISC.2005.12.034MaRDI QIDQ2433705zbMATH OpenOpenAlexFDO

Authors Simone Dantas, Sylvain Gravier, Sulamita Klein, Celina M. H. de Figueiredo

Publication date 30 October 2006

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2005.12.034

zbMATH Keywords

algorithms and data structuresskew partitioncomputational and structural complexity2-sat

Mathematics Subject Classification ID

Data structures (68P05) Nonnumerical algorithms (68W05)

Cites work

• scientific article; zbMATH DE number 1545651 (Why is no real title available?)
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A solution to a colouring problem of P. Erdős
• Colorings and orientations of graphs
• Complexity of graph partition problems
• List Partitions
• List homomorphisms and circular arc graphs
• List homomorphisms to reflexive graphs
• Partitioning chordal graphs into independent sets and cliques
• Star-cutsets and perfect graphs
• The list partition problem for graphs
• The strong perfect graph theorem

Cited in

(3)

• The polynomial dichotomy for three nonempty part sandwich problems
• The external constraint 4 nonempty part sandwich problem
• The polynomial dichotomy for three nonempty part sandwich problems

This page was built for publication: Extended skew partition problem

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