Complexity issues for the sandwich homogeneous set problem

DOI10.1016/j.dam.2010.08.008zbMath1213.05242OpenAlexW2057129198MaRDI QIDQ531596

Arnaud Durand, Michel A. Habib

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.08.008

zbMATH Keywords

homogeneous setscomplexity of enumeration problemsgraph sandwich problems

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Graph Classes and Forbidden Patterns on Three Vertices

Cites Work

• The homogeneous set sandwich problem
• Finding and counting given length cycles
• Note on the homogeneous set sandwich problem
• The pair completion algorithm for the homogeneous set sandwich problem
• Algorithms for the homogeneous set sandwich problem
• Matrix multiplication via arithmetic progressions
• A note on finding all homogeneous set sandwiches
• The graph sandwich problem for \(P_4\)-sparse graphs
• On the complexity of DNA physical mapping
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• An efficient algorithm for solving the homogeneous set sandwich problem
• The graph sandwich problem for 1-join composition is NP-complete
• Competitive graph searches
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Clustering with Partial Information
• Color-coding