Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases

DOI10.1007/s00453-018-0405-xzbMath1390.68354OpenAlexW2788483986MaRDI QIDQ1635706

Rodolphe Giroudeau, Annie Chateau, Mathias Weller, Clément Dallard

Publication date: 1 June 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-018-0405-x

zbMATH Keywords

complexityapproximationlower boundkernelscaffolding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Genetics and epigenetics (92D10) Approximation algorithms (68W25)

Related Items (2)

Instance Guaranteed Ratio on Greedy Heuristic for Genome Scaffolding ⋮ Linearizing Genomes: Exact Methods and Local Search

Uses Software

• SOPRA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
• Fundamentals of parameterized complexity
• Blockers for the stability number and the chromatic number
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• 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
• A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths
• On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs
• Kernelization Lower Bounds by Cross-Composition
• On the complexity of \(k\)-SAT

This page was built for publication: Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases