On the parameterized complexity of maximum degree contraction problem
type: Item
instance of: scholarly article
title: On the parameterized complexity of maximum degree contraction problem
author: Saket Saurabh
author: Prafullkumar Tale
published in: Algorithmica
publication date: 2022-03-25T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/13329/
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7498365
zbMATH Keywords: graph contraction
zbMATH Keywords: maximum degree contraction
zbMATH Keywords: parameterized complexity
zbMATH Keywords: FPT algorithms
zbMATH Keywords: no-poly kernel
zbMATH Keywords: ETH-lower bound
MaRDI profile type: Publication
OpenAlex ID: W4226428923
cites work: On the parameterized complexity of contraction to generalization of trees
cites work: Path Contraction Faster than $2^n$
cites work: Paths to Trees and Cacti
cites work: Split Contraction
cites work: Color-coding
cites work: Edge-contraction problems
cites work: Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
cites work: Parameterized complexity of three edge contraction problems with degree constraints
cites work: On bounded-degree vertex deletion parameterized by treewidth
cites work: Reduction algorithms for graphs of small treewidth
cites work: Contractibility and NP-completeness
cites work: Contracting Few Edges to Remove Forbidden Induced Subgraphs
cites work: A Linear Kernel for Co-Path/Cycle Packing
cites work: Parameterized Algorithms
cites work: Q4268437
cites work: Fundamentals of parameterized complexity
cites work: A generalization of Nemhauser and Trotter's local optimization theorem
cites work: Parametrized complexity theory.
cites work: Kernelization
cites work: On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
cites work: Obtaining planarity by contracting few edges
cites work: Increasing the minimum degree of a graph by contractions
cites work: A faster FPT algorithm for bipartite contraction
cites work: On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
cites work: Obtaining a Bipartite Graph by Contracting Few Edges
cites work: Contracting graphs to paths and trees
cites work: Isolation concepts for efficiently enumerating dense subgraphs
cites work: Lossy Kernels for Graph Contraction Problems
cites work: An FPT algorithm for contraction to cactus
cites work: Slightly Superexponential Parameterized Problems
cites work: On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
cites work: Lossy kernelization
cites work: The computational complexity of disconnected cut and \(2 K_2\)-partition
cites work: Q5710169
cites work: Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
cites work: On the Parameterized Complexity Of Grid Contraction
cites work: A 4 k 2 kernel for feedback vertex set
cites work: On the removal of forbidden graphs by edge-deletion or by edge- contraction
cites work: On the NP-hardness of edge-deletion and -contraction problems
DOI: 10.1007/S00453-021-00897-6
description: scientific article; zbMATH DE number 7498365