On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs

DOI10.1007/978-3-319-26626-8_30zbMath1473.68098OpenAlexW2407019871MaRDI QIDQ3467860

Rodolphe Giroudeau, Annie Chateau, Mathias Weller

Publication date: 5 February 2016

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-26626-8_30

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Genetics and epigenetics (92D10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (8)

On residual approximation in solution extension problems ⋮ Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases ⋮ Approximation algorithms for the scaffolding problem and its generalizations ⋮ On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs ⋮ Instance Guaranteed Ratio on Greedy Heuristic for Genome Scaffolding ⋮ On Residual Approximation in Solution Extension Problems ⋮ Better Approximation Algorithms for Scaffolding Problems ⋮ Linearizing Genomes: Exact Methods and Local Search

Uses Software

• SOPRA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Which problems have strongly exponential complexity?
• Partitions of graphs into one or two independent sets and cliques
• A complexity and approximation framework for the maximization scaffolding problem
• Tight lower bounds for certain parameterized NP-hard problems
• On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs

This page was built for publication: On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs