scientific article; zbMATH DE number 7053259
From MaRDI portal
Publication:5743378
zbMath1421.68072arXiv1812.03155MaRDI QIDQ5743378
Publication date: 10 May 2019
Full work available at URL: https://arxiv.org/abs/1812.03155
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (40)
Hans Bodlaender and the Theory of Kernelization Lower Bounds ⋮ Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds ⋮ Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems ⋮ Uniform Kernelization Complexity of Hitting Forbidden Minors ⋮ New Limits to Classical and Quantum Instance Compression ⋮ Kernelization of Cycle Packing with Relaxed Disjointness Constraints ⋮ AND-compression of NP-complete problems: streamlined proof and minor observations ⋮ Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets ⋮ Kernel for \(K_t\)\textsc{-free Edge Deletion} ⋮ Parameterized analysis and crossing minimization problems ⋮ Sparsification upper and lower bounds for graph problems and not-all-equal SAT ⋮ A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time ⋮ On fair covering and hitting problems ⋮ Kernel bounds for path and cycle problems ⋮ Kernelization Algorithms for Packing Problems Allowing Overlaps ⋮ Polynomial Kernel for Interval Vertex Deletion ⋮ Essentially tight kernels for (weakly) closed graphs ⋮ Unnamed Item ⋮ Parameterized complexity of induced graph matching on claw-free graphs ⋮ The minimum feasible tileset problem ⋮ Exploiting c-Closure in Kernelization Algorithms for Graph Problems ⋮ Parameterized algorithms and kernels for rainbow matching ⋮ On the approximate compressibility of connected vertex cover ⋮ Unnamed Item ⋮ Kernelization hardness of connectivity problems in \(d\)-degenerate graphs ⋮ Lossy kernelization of same-size clustering ⋮ Kernels for packing and covering problems ⋮ Optimal data reduction for graph coloring using low-degree polynomials ⋮ Parameterized certificate dispersal and its variants ⋮ Lower bounds for the happy coloring problems ⋮ Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials ⋮ Parameterized Algorithms and Kernels for Rainbow Matching ⋮ Triangle packing in (sparse) tournaments: approximation and kernelization ⋮ Best-case and worst-case sparsifiability of Boolean CSPs ⋮ A polynomial kernel for bipartite permutation vertex deletion ⋮ Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds ⋮ Lossy kernelization of same-size clustering ⋮ Unnamed Item ⋮ A completeness theory for polynomial (Turing) kernelization ⋮ On sparsification for computing treewidth
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds on kernelization
- Combinatorial and computational aspects of graph packing and graph decomposition
- A linear kernel for a planar connected dominating set
- Lower bounds for kernelizations and other preprocessing procedures
- Looking at the stars
- A parameterized perspective on packing paths of length two
- Faster fixed-parameter tractable algorithms for matching and packing problems
- An improved kernelization for \(P_{2}\)-packing
- A more effective linear kernelization for cluster editing
- On problems without polynomial kernels
- Parametrized complexity theory.
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- Intersection Theorems for Systems of Sets
- Preprocessing of Min Ones Problems: A Dichotomy
- A Problem Kernelization for Graph Packing
- Incompressibility through Colors and IDs
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Two Edge Modification Problems without Polynomial Kernels
- Properties of vertex packing and independence system polyhedra
- Reducibility among Combinatorial Problems
- (Meta) Kernelization
- Parameterized and Exact Computation
- Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
- On the completeness of a generalized matching problem
- Bidimensionality and Geometric Graphs
- Graph-Theoretic Concepts in Computer Science
- Graph-Theoretic Concepts in Computer Science
- Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems
This page was built for publication:
