Algorithms and complexity of sandwich problems in graphs (extended abstract)

DOI10.1007/3-540-57899-4_41zbMath1528.68291OpenAlexW1509241173MaRDI QIDQ6184393

Martin Charles Golumbic, Ron Shamir, Haim Kaplan

Publication date: 5 January 2024

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-57899-4_41

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complement reducible graphs
• Comparability graphs and intersection graphs
• The complexity of reconstructing trees from qualitative characters and subtrees
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A recognition algorithm for the intersection graphs of paths in trees
• On the complexity of DNA physical mapping
• A characterisation of rigid circuit graphs
• The NP-completeness column: an ongoing guide
• Computing the Minimum Fill-In is NP-Complete
• Triangulating 3-Colored Graphs
• Total Ordering Problem
• Complexity and algorithms for reasoning about time
• Circular permutation graphs
• Graph Sandwich Problems
• Two strikes against perfect phylogeny
• The complexity of satisfiability problems
• Transitiv orientierbare Graphen
• Characterizing circular-arc graphs
• Threshold Numbers and Threshold Completions

This page was built for publication: Algorithms and complexity of sandwich problems in graphs (extended abstract)