What's next? Future directions in parameterized complexity
From MaRDI portal
Publication:2908548
DOI10.1007/978-3-642-30891-8_20zbMATH Open1358.68143OpenAlexW33845589MaRDI QIDQ2908548FDOQ2908548
Authors: Dániel Marx 
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_20
Recommendations
Cites Work
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Exact exponential algorithms.
- Finding odd cycle transversals.
- Graph minors. XX: Wagner's conjecture
- A kernelization algorithm for \(d\)-hitting set
- On problems without polynomial kernels
- Almost 2-SAT is fixed-parameter tractable
- Fixed-parameter algorithms for CLOSEST STRING and related problems
- Which problems have strongly exponential complexity?
- Directed tree-width
- Graph minors. XIII: The disjoint paths problem
- An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
- Directed path-width and monotonicity in digraph searching
- Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
- On Multiway Cut Parameterized above Lower Bounds
- Kernelization – Preprocessing with a Guarantee
- Can you beat treewidth?
- Are there any good digraph width measures?
- Closest Substring Problems with Small Distances
- A fixed-parameter algorithm for the directed feedback vertex set problem
- More efficient algorithms for closest string and substring problems
- Title not available (Why is that?)
- ON DISJOINT CYCLES
- Color-coding
- Title not available (Why is that?)
- FPT algorithms for path-transversal and cycle-transversal problems
- Title not available (Why is that?)
- Fixed-parameter tractability of multicut parameterized by the size of the cutset
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Title not available (Why is that?)
- Parameterized graph separation problems
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Digraph measures: Kelly decompositions, games, and orderings
- Improved algorithms for feedback vertex set problems
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- The complexity of satisfiability of small depth circuits
- Vertex packings: Structural properties and algorithms
- Title not available (Why is that?)
- (Meta) Kernelization
- Improved upper bounds for vertex cover
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Title not available (Why is that?)
- Multicut is FPT
- Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
- Some consequences of non-uniform conditions on uniform classes
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Bidimensionality: new connections between FPT algorithms and PTASs
- An improved kernelization algorithm for \(r\)-set packing
- Fast FAST
- Tournament immersion and cutwidth
- Parameterized algorithms for feedback set problems and their duals in tournaments
- Title not available (Why is that?)
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- DAG-Width and Parity Games
- Subexponential Parameterized Algorithm for Minimum Fill-In
- On the complexity of some colorful problems parameterized by treewidth
- 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
- Linear FPT reductions and computational lower bounds
- Kernelization: new upper and lower bound techniques
- A Basic Parameterized Complexity Primer
- The Parameterized Complexity of Counting Problems
- Title not available (Why is that?)
- Parameterized complexity of finding subgraphs with hereditary properties.
- Obtaining a planar graph by vertex deletion
- Parameterized Complexity of Eulerian Deletion Problems
- Planar Subgraph Isomorphism Revisited
- Subgraph Isomorphism in Planar Graphs and Related Problems
- Title not available (Why is that?)
- On the complexity of circuit satisfiability
- Distortion Is Fixed Parameter Tractable
- Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
- Parameterized complexity: exponential speed-up for planar graph problems
- Computing the Deficiency of Housing Markets with Duplicate Houses
- The Bidimensional Theory of Bounded-Genus Graphs
- Title not available (Why is that?)
- Lower bounds on kernelization
- Disjoint paths in tournaments
- Digraph decompositions and monotonicity in digraph searching
- Faster parameterized algorithms for \textsc{Minimum Fill-in}
- An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
- Planarity Allowing Few Error Vertices in Linear Time
- Satisfiability certificates verifiable in subexponential time
Cited In (16)
- Multi-Budgeted Directed Cuts
- Parameterized resiliency problems
- Parameterized algorithms for generalizations of directed feedback vertex set
- Parametrized complexity: New developments and research frontiers
- Known Algorithms for Edge Clique Cover are Probably Optimal
- A survey of parameterized algorithms and the complexity of edge modification
- The Birth and Early Years of Parameterized Complexity
- A Basic Parameterized Complexity Primer
- Improved Lower Bounds for Graph Embedding Problems
- Tight bounds for parameterized complexity of cluster editing with a small number of clusters
- Integer programming in parameterized complexity: five miniatures
- Parameterized Analysis of Art Gallery and Terrain Guarding
- A tight lower bound for vertex planarization on graphs of bounded treewidth
- Title not available (Why is that?)
- Edge bipartization faster than \(2^k\)
- Integer Programming in Parameterized Complexity: Three Miniatures.
This page was built for publication: What's next? Future directions in parameterized complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2908548)
