Kernelization. Theory of parameterized preprocessing
From MaRDI portal
Research exposition (monographs, survey articles) pertaining to computer science (68-02) General topics in the theory of data (68P01) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) General topics in the theory of algorithms (68W01) Combinatorial optimization (90C27)
Recommendations
Cited in
(only showing first 100 items - show all)- Paths to trees and cacti
- On the approximate compressibility of connected vertex cover
- Parameterized complexity of \textsc{maximum edge colorable subgraph}
- Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
- A parameterized perspective on protecting elections
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- On the parametrized complexity of read-once refutations in UTVPI+ constraint systems
- Sparsification lower bound for linear spanners in directed graphs
- Reflections on kernelizing and computing unrooted agreement forests
- 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
- 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
- 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
- Linear-time parameterized algorithms with limited local resources
- Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
- Star colouring of bounded degree graphs and regular graphs
- 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
- Parameterized analysis and crossing minimization problems
- Parameterized complexity of happy coloring problems
- On the tractability of optimization problems on \(H\)-graphs
- Polynomial kernels for hitting forbidden minors under structural parameterizations
- Optimal-size problem kernels for d-Hitting Set in linear time and space
- Revisiting the parameterized complexity of maximum-duo preservation string mapping
- New reduction rules for the tree bisection and reconnection distance
- Parameterized low-rank binary matrix approximation
- Tree-like unit refutations in Horn constraint systems
- Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
- Alternative parameterizations of \textsc{Metric Dimension}
- New kernels for several problems on planar graphs
- Consensus strings with small maximum distance and small distance sum
- Simultaneous feedback edge set: a parameterized perspective
- 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
- \(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
- On the parameterized complexity of clustering problems for incomplete data
- FPT and kernelization algorithms for the induced tree problem
- Circumventing connectivity for kernelization
- Fixed parameterized algorithms for generalized feedback vertex set problems
- A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
- A single exponential-time FPT algorithm for cactus contraction
- Bidimensionality and kernels
- Kernelization of graph Hamiltonicity: proper \(H\)-graphs
- Kernelization of Whitney switches
- 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
- Bridge-depth characterizes which minor-closed structural parameterizations of vertex cover admit a polynomial kernel
- Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments
- Connecting the dots (with minimum crossings)
- scientific article; zbMATH DE number 7559376 (Why is no real title available?)
- Quick separation in chordal and split graphs
- Approximate Counting of k-Paths: Deterministic and in Polynomial Space
- Packing Arc-Disjoint Cycles in Tournaments
- Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
- The parameterized complexity of motion planning for snake-like robots
- Solving partition problems almost always requires pushing many vertices around
- Packing cycles faster than Erdős-Pósa
- Lossy kernels for connected dominating set on sparse graphs
- Parameterized pre-coloring extension and list coloring problems
- Kernelization of Whitney Switches
- scientific article; zbMATH DE number 7651188 (Why is no real title available?)
- Approximate Turing Kernelization for Problems Parameterized by Treewidth
- Optimal polynomial-time compression for Boolean Max CSP
- Incompressibility of H-free edge modification problems: towards a dichotomy
- Quadratic vertex kernel for split vertex deletion
- Parameterized algorithms for finding highly connected solution
- Conflict free version of covering problems on graphs: classical and parameterized
- Vertex deletion on split graphs: beyond 4-hitting set
- Structural parameterizations of budgeted graph coloring
- Parameterized algorithms for finding highly connected solution
- A polynomial kernel for 3-leaf power deletion
- On data reduction for dynamic vector bin packing
- Diverse Pairs of Matchings
- Sparsification lower bounds for list \(H\)-coloring
- Recognizing k -Leaf Powers in Polynomial Time, for Constant k
- Neighbourhood complexity of graphs of bounded twin-width
- On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
This page was built for publication: Kernelization. Theory of parameterized preprocessing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4646517)
