What’s Next? Future Directions in Parameterized Complexity
From MaRDI portal
Publication:2908548
DOI10.1007/978-3-642-30891-8_20zbMath1358.68143MaRDI QIDQ2908548
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
Related Items
Unnamed Item, Unnamed Item, Improved Lower Bounds for Graph Embedding Problems, Edge bipartization faster than \(2^k\), Parameterized resiliency problems, A tight lower bound for vertex planarization on graphs of bounded treewidth, Tight bounds for parameterized complexity of cluster editing with a small number of clusters, The Birth and Early Years of Parameterized Complexity, A Basic Parameterized Complexity Primer, Known Algorithms for Edge Clique Cover are Probably Optimal
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Lower bounds on kernelization
- Disjoint paths in tournaments
- Exact exponential algorithms.
- On the complexity of some colorful problems parameterized by treewidth
- Digraph decompositions and monotonicity in digraph searching
- Faster parameterized algorithms for \textsc{Minimum Fill-in}
- Finding odd cycle transversals.
- Graph minors. XX: Wagner's conjecture
- Improved upper bounds for vertex cover
- Tournament immersion and cutwidth
- An improved kernelization algorithm for \(r\)-set packing
- Some consequences of non-uniform conditions on uniform classes
- Parameterized graph separation problems
- Parameterized algorithms for feedback set problems and their duals in tournaments
- 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
- A kernelization algorithm for \(d\)-hitting set
- On problems without polynomial kernels
- Almost 2-SAT is fixed-parameter tractable
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Fixed-parameter algorithms for CLOSEST STRING and related problems
- Which problems have strongly exponential complexity?
- Directed tree-width
- Parameterized complexity of finding subgraphs with hereditary properties.
- Graph minors. XIII: The disjoint paths problem
- Obtaining a planar graph by vertex deletion
- 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 the complexity of circuit satisfiability
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- On Multiway Cut Parameterized above Lower Bounds
- A Basic Parameterized Complexity Primer
- Kernelization – Preprocessing with a Guarantee
- Satisfiability Certificates Verifiable in Subexponential Time
- Computing the Deficiency of Housing Markets with Duplicate Houses
- Are There Any Good Digraph Width Measures?
- Parameterized Complexity of Eulerian Deletion Problems
- Closest Substring Problems with Small Distances
- The Bidimensional Theory of Bounded-Genus Graphs
- A fixed-parameter algorithm for the directed feedback vertex set problem
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Linear FPT reductions and computational lower bounds
- More Efficient Algorithms for Closest String and Substring Problems
- An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
- Fast FAST
- Distortion Is Fixed Parameter Tractable
- Kernelization: New Upper and Lower Bound Techniques
- The Complexity of Satisfiability of Small Depth Circuits
- Vertex packings: Structural properties and algorithms
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- ON DISJOINT CYCLES
- Color-coding
- Subgraph Isomorphism in Planar Graphs and Related Problems
- The Parameterized Complexity of Counting Problems
- Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
- Parameterized complexity: exponential speed-up for planar graph problems
- (Meta) Kernelization
- Planarity Allowing Few Error Vertices in Linear Time
- Subexponential Parameterized Algorithm for Minimum Fill-In
- Multicut is FPT
- Fixed-parameter tractability of multicut parameterized by the size of the cutset
- DAG-Width and Parity Games
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
- Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
