On the Complexity of Computing the k-restricted Edge-connectivity of a Graph
DOI10.1007/978-3-662-53174-7_16zbMath1417.68071OpenAlexW2964059668MaRDI QIDQ2827813
Ignasi Sau, Luis Pedro Montejano
Publication date: 21 October 2016
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-662-53174-7_16
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)
Cites Work
- 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
- 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
- A proof of an inequality concerning \(k\)-restricted edge connectivity
- 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
- 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