The external constraint 4 nonempty part sandwich problem

DOI10.1016/j.dam.2010.03.015zbMath1213.05254OpenAlexW2032417107MaRDI QIDQ531610

Rafael B. Teixeira, Simone Dantas, 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

zbMATH Keywords

computational complexitycombinatorial algorithmsgraph sandwich problemsapplied combinatoricslist partitions

Mathematics Subject Classification ID

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

Related Items (9)

Disconnected cuts in claw-free graphs ⋮ Unnamed Item ⋮ The complexity of surjective homomorphism problems-a survey ⋮ Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees ⋮ The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory ⋮ The computational complexity of disconnected cut and \(2 K_2\)-partition ⋮ On disconnected cuts and separators ⋮ Sandwiches missing two ingredients of order four

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

This page was built for publication: The external constraint 4 nonempty part sandwich problem