A parameterized complexity view on collapsing \(k\)-cores
type: Item
instance of: scholarly article
title: A parameterized complexity view on collapsing \(k\)-cores
author: Hendrik Molter
author: Ondřej Suchý
author: Jun-Jie Luo
published in: Theory of Computing Systems
publication date: 2021-12-18T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q27
Mathematics Subject Classification ID: 91D30
zbMATH DE Number: 7449502
zbMATH Keywords: \(r\)-degenerate vertex deletion
zbMATH Keywords: feedback vertex set
zbMATH Keywords: fixed-parameter tractability
zbMATH Keywords: kernelization lower bounds
zbMATH Keywords: graph algorithms
zbMATH Keywords: social network analysis
MaRDI profile type: Publication
full work available at URL: s00224-021-10045-w
OpenAlex ID: W2963602119
cites work: Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
cites work: Fast algorithms for determining (generalized) core groups in social networks
cites work: The complexity of finding harmless individuals in social networks
cites work: Parameterized Inapproximability of Target Set Selection and Generalizations
cites work: Treewidth governs the complexity of target set selection
cites work: Preventing Unraveling in Social Networks: The Anchored $k$-Core Problem
cites work: Kernelization Lower Bounds by Cross-Composition
cites work: A \(c^k n\) 5-approximation algorithm for treewidth
cites work: A naive algorithm for feedback vertex set
cites work: On feedback vertex set: new measure and new structures
cites work: Improved upper bounds for vertex cover
cites work: On the Approximability of Influence in Social Networks
cites work: The bandwidth problem for graphs and matrices—a survey
cites work: Can we create large \(k\)-cores by adding few edges?
cites work: Parameterized complexity of the anchored \(k\)-core problem for directed graphs
cites work: Constant thresholds can make target set selection tractable
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
cites work: Parameterized Algorithms
cites work: Fundamentals of parameterized complexity
cites work: Q5091008
cites work: Tight bounds for parameterized complexity of cluster editing with a small number of clusters
cites work: Q4198056
cites work: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
cites work: Target Set Selection Parameterized by Clique-Width and Maximum Threshold
cites work: Q5111399
cites work: Improved analysis of highest-degree branching for feedback vertex set
cites work: Q2941641
cites work: Treewidth. Computations and approximations
cites work: Faster deterministic \textsc{Feedback Vertex Set}
cites work: Q4904144
cites work: Linear Time Parameterized Algorithms for S <scp>ubset</scp> F <scp>eedback</scp> V <scp>ertex</scp> S <scp>et</scp>
cites work: Q5009469
cites work: The parameterized complexity of editing graphs for bounded degeneracy
cites work: Immunity against Local Influence
cites work: On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
DOI: 10.1007/S00224-021-10045-W
description: scientific article; zbMATH DE number 7449502