A parameterized complexity view on collapsing \(k\)-cores
DOI10.1007/s00224-021-10045-wOpenAlexW2963602119MaRDI QIDQ825978
Ondřej Suchý, Hendrik Molter, Jun-Jie Luo
Publication date: 18 December 2021
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-021-10045-w
graph algorithmsfeedback vertex setfixed-parameter tractabilitysocial network analysis\(r\)-degenerate vertex deletionkernelization lower bounds
Social networks; opinion dynamics (91D30) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
Cites Work
- Parameterized complexity of the anchored \(k\)-core problem for directed graphs
- Fundamentals of parameterized complexity
- Treewidth governs the complexity of target set selection
- On feedback vertex set: new measure and new structures
- Improved upper bounds for vertex cover
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- The parameterized complexity of editing graphs for bounded degeneracy
- On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
- Treewidth. Computations and approximations
- Can we create large \(k\)-cores by adding few edges?
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
- Linear time solvable optimization problems on graphs of bounded clique-width
- Faster deterministic \textsc{Feedback Vertex Set}
- Improved analysis of highest-degree branching for feedback vertex set
- Constant thresholds can make target set selection tractable
- The complexity of finding harmless individuals in social networks
- Fast algorithms for determining (generalized) core groups in social networks
- Tight bounds for parameterized complexity of cluster editing with a small number of clusters
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- On the Approximability of Influence in Social Networks
- The bandwidth problem for graphs and matrices—a survey
- Linear Time Parameterized Algorithms for S <scp>ubset</scp> F <scp>eedback</scp> V <scp>ertex</scp> S <scp>et</scp>
- Kernelization Lower Bounds by Cross-Composition
- Target Set Selection Parameterized by Clique-Width and Maximum Threshold
- Parameterized Inapproximability of Target Set Selection and Generalizations
- A naive algorithm for feedback vertex set
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Immunity against Local Influence
- Preventing Unraveling in Social Networks: The Anchored $k$-Core Problem
- Parameterized Algorithms
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A parameterized complexity view on collapsing \(k\)-cores
