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

zbMATH Keywords

parameterized complexitypolynomial kernel\(k\)-restricted edge-connectivityFPT-algorithmgood edge separationgraph cut

Mathematics Subject Classification ID

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