On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
DOI10.1016/j.tcs.2016.12.006zbMath1356.68107arXiv1502.07659OpenAlexW2576039262MaRDI QIDQ501666
Luis Pedro Montejano, Ignasi Sau
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
parameterized complexitypolynomial kernel\(k\)-restricted edge-connectivityFPT-algorithmgood edge separationgraph cut
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)
Related Items (5)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(k\)-restricted edge-connectivity in triangle-free graphs
- Parameterized graph separation problems
- Strong computational lower bounds via parameterized complexity
- Sufficient conditions for \(\lambda _k\)-optimality in triangle-free graphs
- On the complexity of partitioning graphs into connected subgraphs
- On computing a conditional edge-connectivity of a graph
- Some simplified NP-complete graph problems
- Extraconnectivity of graphs with large girth
- Extraconnectivity of graphs with large minimum degree and girth
- Edge-cuts leaving components of order at least three
- Parametrized complexity theory.
- A proof of an inequality concerning \(k\)-restricted edge connectivity
- A Parameterized Algorithm for Mixed-Cut
- On the Parameterized Complexity of Computing Graph Bisections
- Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask).
- Designing FPT Algorithms for Cut Problems Using Randomized Contractions
- Planar 3DM is NP-complete
- A simple min-cut algorithm
- Kernelization Lower Bounds by Cross-Composition
- Minimum bisection is fixed parameter tractable
- Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism
- The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable
- Parameterized Algorithms
This page was built for publication: On the complexity of computing the \(k\)-restricted edge-connectivity of a graph