Search-space reduction via essential vertices
type: Item
instance of: scholarly article
title: Search-space reduction via essential vertices
zbMATH Open document ID: 1547.05218
author: Benjamin Merlin Bumpus
author: Bart M. P. Jansen
author: Jari J. H. de Kroon
published in: SIAM Journal on Discrete Mathematics
publication date: 2024-09-17T00:00:00Z
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W40
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 7914821
zbMATH Keywords: fixed-parameter tractability
zbMATH Keywords: essential vertices
zbMATH Keywords: covering versus packing
MaRDI profile type: MaRDI publication profile
cites work: Presolve Reductions in Mixed Integer Programming
cites work: Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
cites work: Experiments on data reduction for optimal domination in networks
cites work: Q3993087
cites work: Lower Bounds for Kernelization
cites work: (Meta) Kernelization
cites work: A cubic kernel for feedback vertex set and loop cutset
cites work: Chordal editing is fixed-parameter tractable
cites work: Improved upper bounds for vertex cover
cites work: A fixed-parameter algorithm for the directed feedback vertex set problem
cites work: Packing non-zero \(A\)-paths in group-labelled graphs
cites work: New Hardness Results for Routing on Disjoint Paths
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Parameterized Algorithms
cites work: Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
cites work: Preprocessing to reduce the search space: antler structures for feedback vertex set
cites work: Fundamentals of parameterized complexity
cites work: New Limits to Classical and Quantum Instance Compression
cites work: Measuring what matters: a hybrid approach to dynamic programming with treewidth
cites work: On Independent Circuits Contained in a Graph
cites work: The Lost Continent of Polynomial Time: Preprocessing and Kernelization
cites work: Kernelization
cites work: On the odd-minor variant of Hadwiger's conjecture
cites work: Algorithmic graph theory and perfect graphs
cites work: Losing Treewidth by Separating Subsets
cites work: Parameterized complexity of vertex deletion into perfect graph classes
cites work: Vertex deletion parameterized by elimination distance and even less
cites work: Approximation and Kernelization for Chordal Vertex Deletion
cites work: On the Computational Complexity of Combinatorial Problems
cites work: On the Parameterized Complexity of Approximating Dominating Set
cites work: On the power of unique 2-prover 1-round games
cites work: Q4967164
cites work: Representative Sets and Irrelevant Vertices
cites work: The even-path problem for graphs and digraphs
cites work: Detecting Feedback Vertex Sets of Size k in O ⋆ (2.7 k ) Time
cites work: Wheel-Free Deletion Is W[2]-Hard
cites work: Kernelization – Preprocessing with a Guarantee
cites work: Faster Parameterized Algorithms Using Linear Programming
cites work: Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
cites work: Perturbation Resilience
cites work: Vertex packings: Structural properties and algorithms
cites work: Finding odd cycle transversals.
cites work: Graph minors. V. Excluding a planar graph
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: NP is as easy as detecting unique solutions
DOI: 10.1137/23M1589347
description: scientific article; zbMATH DE number 7914821