FPT Suspects and Tough Customers: Open Problems of Downey and Fellows

DOI10.1007/978-3-642-30891-8_19zbMath1358.68132MaRDI QIDQ2908547

Dániel Marx, Fedor V. Fomin

Publication date: 5 September 2012

Published in: The Multivariate Algorithmic Revolution and Beyond (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-30891-8_19

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

Related Items

On the complexity of connection games, Chain minors are FPT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• FPT algorithms for path-transversal and cycle-transversal problems
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• On the size of jump-critical ordered sets
• Parameterized graph separation problems
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Graph minors XXIII. Nash-Williams' immersion conjecture
• The planar multiterminal cut problem
• The directed subgraph homeomorphism problem
• The parameterized complexity of sequence alignment and consensus
• On algorithmic applications of the immersion order: An overview of ongoing work presented at the Third Slovenian International Conference on Graph Theory
• An improved algorithm for the jump number problem
• Which problems have strongly exponential complexity?
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Computing crossing numbers in quadratic time
• Graph minors. XIII: The disjoint paths problem
• Well quasi ordering finite posets and formal languages
• An improved parameterized algorithm for the minimum node multiway cut problem
• Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
• A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals
• On Multiway Cut Parameterized above Lower Bounds
• A 4 k ² kernel for feedback vertex set
• Clustering with Local Restrictions
• Deciding first-order properties of locally tree-decomposable structures
• A fixed-parameter algorithm for the directed feedback vertex set problem
• Recognizing Polymatroids Associated with Hypergraphs
• Finding k Disjoint Paths in a Directed Planar Graph
• The Complexity of Multiterminal Cuts
• Color-coding
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Computing crossing numbers in quadratic time
• Finding topological subgraphs is fixed-parameter tractable
• Computing and Combinatorics