The external constraint 4 nonempty part sandwich problem
From MaRDI portal
Publication:531610
DOI10.1016/j.dam.2010.03.015zbMath1213.05254MaRDI QIDQ531610
Simone Dantas, Rafael B. Teixeira, Celina M. Herrera de Figueiredo
Publication date: 19 April 2011
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2010.03.015
computational complexity; combinatorial algorithms; graph sandwich problems; applied combinatorics; list partitions
68Q25: Analysis of algorithms and problem complexity
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
On disconnected cuts and separators, Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees
Cites Work
- Unnamed Item
- Unnamed Item
- The homogeneous set sandwich problem
- List matrix partitions of chordal graphs
- The strong perfect graph theorem
- \(2K_{2}\) vertex-set partition into nonempty parts
- Star-cutsets and perfect graphs
- Complexity and algorithms for graph and hypergraph sandwich problems
- Bounded degree interval sandwich problems
- Matrix sandwich problems
- 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
- Matrix partitions of perfect graphs
- Recognizing Berge graphs
- The sandwich problem for cutsets: clique cutset, \(k\)-star cutset
- Skew partition sandwich problem is NP-complete
- The Complexity of the List Partition Problem for Graphs
- Decomposition of Directed Graphs
- Two-Processor Scheduling with Start-Times and Deadlines
- List Partitions
- FindingH-partitions efficiently
- Graph Sandwich Problems
- Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
- Fast Skew Partition Recognition
- The polynomial dichotomy for three nonempty part sandwich problems
