The sandwich problem for cutsets: clique cutset, k-star cutset

DOI10.1016/J.DAM.2006.03.023zbMATH Open1097.05029OpenAlexW1999061086MaRDI QIDQ2500527FDOQ2500527

Authors: R. B. Teixeira, Celina M. H. de Figueiredo 

Publication date: 17 August 2006

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

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

Recommendations

• Skew partition sandwich problem is NP-complete
• scientific article; zbMATH DE number 6423755
• The sandwich problem for decompositions and almost monotone properties
• Graph Sandwich Problems
• On decision and optimization (\(k\),\(l\))-graph sandwich problems

zbMATH Keywords

graph algorithmsrecognition problemsandwich problemsanalysis of algorithms and problem complexityvertex cutsets

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Title not available (Why is that?)
• Bounded degree interval sandwich problems
• Graph Sandwich Problems
• Decomposition by clique separators
• The homogeneous set sandwich problem
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• Star-cutsets and perfect graphs
• On stable cutsets in graphs
• Title not available (Why is that?)
• An algorithm for finding clique cut-sets
• Complexity and algorithms for graph and hypergraph sandwich problems
• Matrix sandwich problems
• The graph sandwich problem for 1-join composition is NP-complete
• On decision and optimization (\(k\),\(l\))-graph sandwich problems
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (8)

• The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
• The polynomial dichotomy for three nonempty part sandwich problems
• The graph sandwich problem for \(P_4\)-sparse graphs
• The P versus NP-complete dichotomy of some challenging problems in graph theory
• The external constraint 4 nonempty part sandwich problem
• Skew partition sandwich problem is NP-complete
• The sandwich problem for decompositions and almost monotone properties
• The polynomial dichotomy for three nonempty part sandwich problems

This page was built for publication: The sandwich problem for cutsets: clique cutset, \(k\)-star cutset

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