Building large \(k\)-cores from sparse graphs

DOI10.1016/j.jcss.2022.10.002OpenAlexW3005640923MaRDI QIDQ2678255

Danil Sagunov, Kirill Simonov, Fedor V. Fomin

Publication date: 9 January 2023

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2022.10.002

zbMATH Keywords

treewidthvertex coverparameterized complexity\(k\)-core

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• Parameterized complexity of the anchored \(k\)-core problem for directed graphs
• Editing graphs to satisfy degree constraints: a parameterized approach
• Infeasibility of instance compression and succinct PCPs for NP
• A parameterized complexity view on collapsing \(k\)-cores
• \(k\)-core decomposition of internet graphs: hierarchies, self-similarity and measurement biases
• On problems without polynomial kernels
• An application of simultaneous diophantine approximation in combinatorial optimization
• Can we create large \(k\)-cores by adding few edges?
• Finding even subgraphs even faster
• A note on a theorem of Erdős and Gallai
• Editing to a connected graph of given degrees
• Understanding Edge Connectivity in the Internet through Core Decomposition
• Integer Programming with a Fixed Number of Variables
• Minkowski's Convex Body Theorem and Integer Programming
• Tight lower bounds on the matching number in a graph with given maximum degree
• Kernelization
• Communication and Coordination in Social Networks
• Kernelization Lower Bounds Through Colors and IDs
• Editing to Connected F-Degree Graph
• Preventing Unraveling in Social Networks: The Anchored $k$-Core Problem
• Parameterized Algorithms
• A survey of parameterized algorithms and the complexity of edge modification