Kernelization
From MaRDI portal
Publication:4646517
DOI10.1017/9781107415157zbMath1426.68003OpenAlexW4211121212MaRDI QIDQ4646517
Meirav Zehavi, Saket Saurabh, Daniel Lokshtanov, Fedor V. Fomin
Publication date: 14 January 2019
Full work available at URL: https://doi.org/10.1017/9781107415157
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) General topics in the theory of algorithms (68W01) General topics in the theory of data (68P01)
Related Items (only showing first 100 items - show all)
Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies ⋮ On the proper orientation number of chordal graphs ⋮ Star colouring of bounded degree graphs and regular graphs ⋮ Compactors for parameterized counting problems ⋮ Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ Hans Bodlaender and the Theory of Kernelization Lower Bounds ⋮ Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds ⋮ A Retrospective on (Meta) Kernelization ⋮ Parameterized complexity of \(d\)-hitting set with quotas ⋮ On the parameterized complexity of maximum degree contraction problem ⋮ Parameterized complexity of categorical clustering with size constraints ⋮ Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel ⋮ Well-partitioned chordal graphs ⋮ On structural parameterizations of the offensive alliance problem ⋮ Exact and parameterized algorithms for read-once refutations in Horn constraint systems ⋮ From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability ⋮ Parameterized complexity of directed spanner problems ⋮ A polynomial kernel for funnel arc deletion set ⋮ Simultaneous feedback edge set: a parameterized perspective ⋮ Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments ⋮ Parameterized analysis and crossing minimization problems ⋮ Finding a maximum minimal separator: graph classes and fixed-parameter tractability ⋮ A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion ⋮ Packing arc-disjoint cycles in tournaments ⋮ Diversity of solutions: an exploration through the lens of fixed-parameter tractability theory ⋮ Preprocessing to reduce the search space: antler structures for feedback vertex set ⋮ Completion to chordal distance-hereditary graphs: a quartic vertex-kernel ⋮ On the parameterized complexity of grid contraction ⋮ Elimination Distances, Blocking Sets, and Kernels for Vertex Cover ⋮ \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms ⋮ Building large \(k\)-cores from sparse graphs ⋮ Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance ⋮ Improved kernels for tracking paths ⋮ Parameterized complexity of happy coloring problems ⋮ On the tractability of optimization problems on \(H\)-graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the parameterized complexity of clustering problems for incomplete data ⋮ Polynomial kernels for hitting forbidden minors under structural parameterizations ⋮ FPT and kernelization algorithms for the induced tree problem ⋮ Circumventing connectivity for kernelization ⋮ Fixed parameterized algorithms for generalized feedback vertex set problems ⋮ Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space ⋮ A cubic vertex-kernel for \textsc{Trivially Perfect Editing} ⋮ A single exponential-time FPT algorithm for cactus contraction ⋮ Revisiting the parameterized complexity of maximum-duo preservation string mapping ⋮ New reduction rules for the tree bisection and reconnection distance ⋮ The Parameterized Complexity of Motion Planning for Snake-Like Robots ⋮ Parameterized low-rank binary matrix approximation ⋮ Approximate Turing Kernelization for Problems Parameterized by Treewidth ⋮ Tree-like unit refutations in Horn constraint systems ⋮ Quadratic vertex kernel for split vertex deletion ⋮ Refined notions of parameterized enumeration kernels with applications to matching cut enumeration ⋮ Paths to trees and cacti ⋮ On the approximate compressibility of connected vertex cover ⋮ Parameterized complexity of \textsc{maximum edge colorable subgraph} ⋮ Unnamed Item ⋮ Conflict free version of covering problems on graphs: classical and parameterized ⋮ Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization ⋮ Alternative parameterizations of \textsc{Metric Dimension} ⋮ New kernels for several problems on planar graphs ⋮ A parameterized perspective on protecting elections ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ Parameterized algorithms for finding highly connected solution ⋮ Vertex deletion on split graphs: beyond 4-hitting set ⋮ On the parametrized complexity of Read-once refutations in UTVPI+ constraint systems ⋮ Subset feedback vertex set in chordal and split graphs ⋮ Structural parameterizations of budgeted graph coloring ⋮ Solving Partition Problems Almost Always Requires Pushing Many Vertices Around ⋮ Bidimensionality and Kernels ⋮ Sparsification lower bound for linear spanners in directed graphs ⋮ Consensus strings with small maximum distance and small distance sum ⋮ Connecting the dots (with minimum crossings) ⋮ Quick separation in chordal and split graphs ⋮ Approximate Counting of k-Paths: Deterministic and in Polynomial Space ⋮ Packing Arc-Disjoint Cycles in Tournaments ⋮ Packing Cycles Faster Than Erdos--Posa ⋮ Reflections on kernelizing and computing unrooted agreement forests ⋮ Kernelization of Graph Hamiltonicity: Proper $H$-Graphs ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Incompressibility of \(H\)-free edge modification problems: towards a dichotomy ⋮ Parameterized and exact algorithms for finding a read-once resolution refutation in 2CNF formulas ⋮ Defensive alliances in graphs ⋮ Kernelization of Whitney Switches ⋮ Kernelization of Whitney Switches ⋮ Parameterized complexity of maximum edge colorable subgraph ⋮ Revising Johnson's table for the 21st century ⋮ (Sub)linear kernels for edge modification problems toward structured graph classes ⋮ Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds ⋮ Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size ⋮ Parameterized Pre-Coloring Extension and List Coloring Problems ⋮ Eternal vertex cover on bipartite graphs ⋮ Lossy kernelization of same-size clustering ⋮ Output sensitive fault tolerant maximum matching ⋮ Parameterized complexity of set-restricted disjoint paths on chordal graphs ⋮ Partial vertex cover on graphs of bounded degeneracy ⋮ Parameterized algorithms for finding highly connected solution ⋮ Linear-time parameterized algorithms with limited local resources ⋮ A polynomial kernel for 3-leaf power deletion
This page was built for publication: Kernelization
