Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases
From MaRDI portal
Publication:1635706
Recommendations
- On the complexity of scaffolding problems: from cliques to sparse graphs
- New polynomial-time algorithm around the scaffolding problem
- A complexity and approximation framework for the maximization scaffolding problem
- Approximation algorithms for the scaffolding problem and its generalizations
- Better approximation algorithms for scaffolding problems
Cites work
- A complexity and approximation framework for the maximization scaffolding problem
- A refined complexity analysis of finding the most vital edges for undirected shortest paths
- Blockers for the stability number and the chromatic number
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
- Fundamentals of parameterized complexity
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 566078 (Why is no real title available?)
- scientific article; zbMATH DE number 1953201 (Why is no real title available?)
- Kernelization Lower Bounds by Cross-Composition
- Lower bounds based on the exponential time hypothesis
- On the complexity of k-SAT
- On the complexity of scaffolding problems: from cliques to sparse graphs
- Partitions of graphs into one or two independent sets and cliques
- The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
- Tight lower bounds for certain parameterized NP-hard problems
- Which problems have strongly exponential complexity?
Cited in
(10)- On the linearization of scaffolds sharing repeated contigs
- Producing genomic sequences after genome scaffolding with ambiguous paths: complexity, approximation and lower bounds
- New polynomial-time algorithm around the scaffolding problem
- A complexity and approximation framework for the maximization scaffolding problem
- Approximation algorithms for the scaffolding problem and its generalizations
- Instance guaranteed ratio on greedy heuristic for genome scaffolding
- Linearizing genomes: exact methods and local search
- On the complexity of scaffolding problems: from cliques to sparse graphs
- Better approximation algorithms for scaffolding problems
- An Improved Approximation Algorithm for Scaffold Filling to Maximize the Common Adjacencies
This page was built for publication: Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1635706)
