Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases
From MaRDI portal
Publication:1635706
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
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
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
