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

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)

Related Items (5)

Link fault tolerance of BC networks and folded hypercubes on \(h\)-extra \(r\)-component edge-connectivity ⋮ Concentration behavior: 50 percent of \(h\)-extra edge connectivity of pentanary \(n\)-cube with exponential faulty edges ⋮ An O(log(N)) Algorithm View: Reliability Evaluation of Folded-crossed Hypercube in Terms of h-extra Edge-connectivity ⋮ Unnamed Item ⋮ The \(h\)-restricted connectivity of the generalized hypercubes

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