Building large k-cores from sparse graphs

DOI10.4230/LIPICS.MFCS.2020.35MaRDI QIDQ5089202FDOQ5089202

Authors: Fedor V. Fomin, Danil Sagunov, Kirill Simonov 

Publication date: 18 July 2022

Full work available at URL: https://arxiv.org/abs/2002.07612

Recommendations

• Building large \(k\)-cores from sparse graphs
• Can we create large \(k\)-cores by adding few edges?
• On the robustness of random \(k\)-cores
• A parameterized complexity view on collapsing \(k\)-cores
• A parameterized complexity view on collapsing \(k\)-cores

zbMATH Keywords

treewidthparameterized complexityvertex cover\(k\)-core

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Parameterized complexity of the anchored \(k\)-core problem for directed graphs
• Integer Programming with a Fixed Number of Variables
• Preventing unraveling in social networks: the anchored \(k\)-core problem
• Minkowski's Convex Body Theorem and Integer Programming
• Communication and Coordination in Social Networks
• Parameterized algorithms
• Title not available (Why is that?)
• Kernelization lower bounds through colors and IDs
• A note on a theorem of Erdős and Gallai
• An application of simultaneous diophantine approximation in combinatorial optimization
• Graph theory
• Editing graphs to satisfy degree constraints: a parameterized approach
• Editing to a connected graph of given degrees
• Editing to connected \(f\)-degree graph
• Can we create large \(k\)-cores by adding few edges?
• A parameterized complexity view on collapsing \(k\)-cores
• Preventing unraveling in social networks: the anchored \(k\)-core problem
• \(k\)-core decomposition of internet graphs: hierarchies, self-similarity and measurement biases
• Finding even subgraphs even faster
• Tight lower bounds on the matching number in a graph with given maximum degree
• Understanding edge connectivity in the Internet through core decomposition

Cited In (5)

• Targeted \(k\)-node collapse problem: towards understanding the robustness of local \(k\)-core structure
• Hierarchical cycle-tree packing model for optimal \(K\)-core attack
• Can we create large \(k\)-cores by adding few edges?
• Minimum k‐cores and the k‐core polytope
• Building large \(k\)-cores from sparse graphs

This page was built for publication: Building large \(k\)-cores from sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5089202)