Can we create large \(k\)-cores by adding few edges?

DOI10.1007/978-3-319-90530-3_8zbMath1485.68177OpenAlexW2802741730MaRDI QIDQ1625143

Nimrod Talmon, Rajesh Chitnis

Publication date: 28 November 2018

Full work available at URL: https://doi.org/10.1007/978-3-319-90530-3_8

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

A parameterized complexity view on collapsing \(k\)-cores, Building large \(k\)-cores from sparse graphs, A survey of parameterized algorithms and the complexity of edge modification, Unnamed Item