On the complexity of computing the \(k\)-restricted edge-connectivity of a graph

DOI10.1016/j.tcs.2016.12.006zbMath1356.68107arXiv1502.07659MaRDI QIDQ501666

Ignasi Sau, Luis Pedro Montejano

Publication date: 9 January 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

parameterized complexity; polynomial kernel; \(k\)-restricted edge-connectivity; FPT-algorithm; good edge separation; graph cut

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C40: Connectivity