Extended skew partition problem

DOI10.1016/J.DISC.2005.12.034zbMATH Open1178.68640OpenAlexW2031394890MaRDI QIDQ2433705FDOQ2433705

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

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

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)