Kernelization: new upper and lower bound techniques
From MaRDI portal
Recommendations
Cites work
- (Meta) Kernelization
- \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves
- A cubic kernel for feedback vertex set and loop cutset
- A Linear Kernel for Planar Feedback Vertex Set
- A more effective linear kernelization for cluster editing
- A partial k-arboretum of graphs with bounded treewidth
- A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
- A Problem Kernelization for Graph Packing
- A quadratic kernel for feedback vertex set
- Advice classes of parametrized tractability
- Algorithmic lower bounds for problems parameterized by clique-width
- An algebraic theory of graph reduction
- Approximation algorithms for NP-complete problems on planar graphs
- Automata, Languages and Programming
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Bidimensionality and kernels
- Crown structures for vertex cover kernelization
- Data reduction, exact, and heuristic algorithms for clique cover
- edge dominating set: Efficient Enumeration-Based Exact Algorithms
- Every planar map is four colorable. I: Discharging
- Exact Algorithms for Cluster Editing: Evaluation and Experiments
- Experiments on data reduction for optimal domination in networks
- Fixed-parameter algorithms for Kemeny rankings
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual
- Graph minors. III. Planar tree-width
- Graph minors. XIII: The disjoint paths problem
- Graph minors. XX: Wagner's conjecture
- scientific article; zbMATH DE number 5883528 (Why is no real title available?)
- scientific article; zbMATH DE number 5485524 (Why is no real title available?)
- scientific article; zbMATH DE number 5725105 (Why is no real title available?)
- scientific article; zbMATH DE number 1323192 (Why is no real title available?)
- scientific article; zbMATH DE number 1341905 (Why is no real title available?)
- scientific article; zbMATH DE number 475614 (Why is no real title available?)
- scientific article; zbMATH DE number 1507224 (Why is no real title available?)
- scientific article; zbMATH DE number 795221 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Improved algorithms for path, matching, and packing problems
- Incompressibility through Colors and IDs
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Kernels for feedback arc set in tournaments
- Linear Kernel for Planar Connected Dominating Set
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- Mathematical Foundations of Computer Science 2004
- Mathematical Foundations of Computer Science 2005
- Minimum leaf out-branching and related problems
- Nondeterminism within $P^ * $
- On finding directed trees with many leaves
- On fixed-parameter tractability and approximability of NP optimization problems
- On Problems without Polynomial Kernels (Extended Abstract)
- On the computational hardness based on linear fpt-reductions
- On the existence of subexponential parameterized algorithms
- Parameterized complexity of Vertex Cover variants
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Parametrized complexity theory.
- Planar capacitated dominating set is \(W[1]\)-hard
- Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor
- Polynomial-time data reduction for dominating set
- Quadratic Kernelization for Convex Recoloring of Trees
- Reduction algorithms for graphs of small treewidth
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- SOFSEM 2006: Theory and Practice of Computer Science
- Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
- Strong computational lower bounds via parameterized complexity
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The parameterized complexity of the induced matching problem
- Tight lower bounds for certain parameterized NP-hard problems
- Two edge modification problems without polynomial kernels
- Vertex packings: Structural properties and algorithms
Cited in
(78)- Kernelization lower bounds for finding constant-size subgraphs
- Change-making problems revisited: a parameterized point of view
- Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
- Multivariate complexity analysis of Swap Bribery
- Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
- An improved kernel for max-bisection above tight lower bound
- A refined branching algorithm for the maximum satisfiability problem
- Polynomial kernels for hitting forbidden minors under structural parameterizations
- Constant thresholds can make target set selection tractable
- On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments
- Using patterns to form homogeneous teams
- A refined complexity analysis of degree anonymization in graphs
- A complete parameterized complexity analysis of bounded planning
- Parameterized complexity of control and bribery for \(d\)-approval elections
- Possible winner problems on partial tournaments: a parameterized study
- Tractability, hardness, and kernelization lower bound for and/or graph solution
- Knapsack problems: a parameterized point of view
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- A cubic-vertex kernel for flip consensus tree
- Towards optimal kernel for edge-disjoint triangle packing
- A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
- Hitting forbidden minors: approximation and kernelization
- FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
- Parameterized complexity of control and bribery for \(d\)-approval elections
- Improved parameterized algorithms for above average constraint satisfaction
- Linear-time computation of a linear problem kernel for dominating set on planar graphs
- Kernelization -- preprocessing with a guarantee
- Studies in Computational Aspects of Voting
- What's next? Future directions in parameterized complexity
- Clique Cover and Graph Separation
- Lower bounds for kernelization
- Parameterized algorithms and kernels for 3-hitting set with parity constraints
- An improved kernel for planar connected dominating set
- Kernelization techniques and its applications to parameterized computation
- Measuring indifference: unit interval vertex deletion
- On making a distinguished vertex minimum degree by vertex deletion
- Polynomial kernels for proper interval completion and related problems
- Cross-composition: a new technique for kernelization lower bounds
- (Meta) kernelization
- Kernels: Annotated, Proper and Induced
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Planar graph vertex partition for linear problem kernels
- The parameterized complexity of local search for TSP, more refined
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Incremental list coloring of graphs, parameterized by conservation
- Two-layer planarization parameterized by feedback edge set
- Improved linear problem kernel for planar connected dominating set
- Data reduction for graph coloring problems
- Polynomial kernels for proper interval completion and related problems
- Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
- On making directed graphs transitive
- Graph-based data clustering with overlaps
- Lower bounds on kernelization
- Towards optimal and expressive kernelization for \(d\)-hitting set
- On the parameterized complexity of computing balanced partitions in graphs
- Recent developments in kernelization: a survey
- Kernelization Lower Bounds by Cross-Composition
- Hans Bodlaender and the Theory of Kernelization Lower Bounds
- Fixed-parameter algorithms for DAG partitioning
- On making a distinguished vertex of minimum degree by vertex deletion
- Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring
- An Efficient Algorithm for Computing Kernel Function Defined with Anti-unification
- STACS 2005
- scientific article; zbMATH DE number 7053262 (Why is no real title available?)
- Confluence in data reduction: bridging graph transformation and kernelization
- Confluence in data reduction: bridging graph transformation and kernelization
- Faster existential FO model checking on posets
- On kernel inclusions
- Recognizing k -Leaf Powers in Polynomial Time, for Constant k
- Kernelization for feedback vertex set via elimination distance to a forest
- Kernel bounds for disjoint cycles and disjoint paths
- Solving MAX-\(r\)-SAT above a tight lower bound
- A generalization of Nemhauser and Trotter's local optimization theorem
- The role of twins in computing planar supports of hypergraphs
- On parameterized independent feedback vertex set
- Average parameterization and partial kernelization for computing medians
- On bounded-degree vertex deletion parameterized by treewidth
- Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique
This page was built for publication: Kernelization: new upper and lower bound techniques
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3656848)
