On decision and optimization (\(k\),\(l\))-graph sandwich problems

DOI10.1016/j.dam.2004.02.008zbMath1102.68091OpenAlexW2039144690MaRDI QIDQ1887051

Simone Dantas, Celina M. Herrera de Figueiredo, Luérbio Faria

Publication date: 23 November 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2004.02.008

zbMATH Keywords

NP-complete problemsPartition problemsMax-SNP-hard problemsSandwich problems

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (13)

The pair completion algorithm for the homogeneous set sandwich problem ⋮ Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs ⋮ Edge clique partition in \((k,\ell)\)-graphs ⋮ The polynomial dichotomy for three nonempty part sandwich problems ⋮ The polynomial dichotomy for three nonempty part sandwich problems ⋮ The external constraint 4 nonempty part sandwich problem ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory ⋮ The sandwich problem for cutsets: clique cutset, \(k\)-star cutset ⋮ On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs ⋮ The graph sandwich problem for \(P_4\)-sparse graphs ⋮ On the Complexity of Probe and Sandwich Problems for Generalized Threshold Graphs ⋮ The P4-sparse Graph Sandwich Problem ⋮ Partitions and well-coveredness: the graph sandwich problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The homogeneous set sandwich problem
• Optimization, approximation, and complexity classes
• Some simplified NP-complete graph problems
• Complexity and algorithms for graph and hypergraph sandwich problems
• The complexity of some problems related to GRAPH 3-COLORABILITY
• Bounded degree interval sandwich problems
• Matrix sandwich problems
• The graph sandwich problem for 1-join composition is NP-complete
• Partitions of graphs into one or two independent sets and cliques
• Complexity of graph partition problems
• Graph Sandwich Problems
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques

This page was built for publication: On decision and optimization (\(k\),\(l\))-graph sandwich problems