The pair completion algorithm for the homogeneous set sandwich problem

DOI10.1016/j.ipl.2005.12.010zbMath1186.68329OpenAlexW2131517264MaRDI QIDQ844163

Claudson F. Bornstein, Celina M. Herrera de Figueiredo, Vinícius G. Pereira de Sá

Publication date: 18 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.12.010

zbMATH Keywords

analysis of algorithmsgraph algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Complexity issues for the sandwich homogeneous set problem, The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem, Competitive graph searches, On the bi-enhancement of chordal-bipartite probe graphs

Cites Work

• Unnamed Item
• Unnamed Item
• The homogeneous set sandwich problem
• Note on the homogeneous set sandwich problem
• Algorithms for the homogeneous set sandwich problem
• A note on finding all homogeneous set sandwiches
• Complexity and algorithms for graph and hypergraph sandwich problems
• Bounded degree interval sandwich problems
• An efficient algorithm for solving the homogeneous set sandwich problem
• The graph sandwich problem for 1-join composition is NP-complete
• On decision and optimization (\(k\),\(l\))-graph sandwich problems
• Normal hypergraphs and the perfect graph conjecture
• Efficient and Practical Algorithms for Sequential Modular Decomposition
• Graph Sandwich Problems
• Depth-First Search and Linear Graph Algorithms