scientific article; zbMATH DE number 7053261

Publication date: 10 May 2019

Full work available at URL: https://dl.acm.org/citation.cfm?id=2095124

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matroids and geometric lattices (05B35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Deterministic Truncation of Linear Matroids ⋮ New Limits to Classical and Quantum Instance Compression ⋮ Parameterized complexity of satisfying almost all linear equations over $\mathbb F_2$ ⋮ Preprocessing subgraph and minor problems: when does a small vertex cover help? ⋮ A faster FPT algorithm for bipartite contraction ⋮ A completeness theory for polynomial (Turing) kernelization

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Fundamentals of parameterized complexity
Lower bounds on kernelization
Separator-based data reduction for signed graph balancing
Infeasibility of instance compression and succinct PCPs for NP
Finding odd cycle transversals.
Parameterized graph separation problems
Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
The multi-multiway cut problem
Comparing trees via crossing minimization
On problems without polynomial kernels
Almost 2-SAT is fixed-parameter tractable
A parameterized view on matroid optimization problems
Parameterized and exact computation. 4th international workshop, IWPEC 2009, Copenhagen, Denmark, September 10--11, 2009. Revised selected papers
PRIMES is in P
Combinatorial optimization. Polyhedra and efficiency (3 volumes)
An improved parameterized algorithm for the minimum node multiway cut problem
Planar graph bipartization in linear time
Parametrized complexity theory.
Applications of Menger's graph theorem
Vertex Cover: Further Observations and Further Improvements
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
Proceedings of the forty-third annual ACM symposium on Theory of computing
Kernels for Feedback Arc Set In Tournaments
On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications
On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
A fixed-parameter algorithm for the directed feedback vertex set problem
The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs
Wheel-Free Deletion Is W[2-Hard]
On the power of unique 2-prover 1-round games
O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
A Cubic Kernel for Feedback Vertex Set
Algorithm Engineering for Optimal Graph Bipartization
Iterative Compression for Exactly Solving NP-Hard Minimization Problems
Incompressibility through Colors and IDs
Kernel Bounds for Disjoint Cycles and Disjoint Paths
Simpler Parameterized Algorithm for OCT
A Faster Fixed-Parameter Approach to Drawing Binary Tanglegrams
Two Edge Modification Problems without Polynomial Kernels
Vertex packings: Structural properties and algorithms
A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
(Meta) Kernelization
Bidimensionality and Geometric Graphs
Multicut is FPT
Fixed-parameter tractability of multicut parameterized by the size of the cutset
Experimental and Efficient Algorithms

This page was built for publication: