The complexity of mixed-connectivity

DOI10.1007/s10479-021-04330-7OpenAlexW3206459271MaRDI QIDQ2070706

Sergio Cabello, Édouard Bonnet

Publication date: 24 January 2022

Published in: Annals of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

NP-completenessedge-connectivityvertex-connectivityparameterized complexitymixed-connectivitymixed-cut

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) 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
• Fundamentals of parameterized complexity
• The disjoint paths problem in quadratic time
• Implicit branching and parameterized partial cover problems
• Graph minors. XIII: The disjoint paths problem
• Mixed connectivity properties of random graphs and some special graphs
• The maximum vertex coverage problem on bipartite graphs
• A Parameterized Algorithm for Mixed-Cut
• Mixed connectivity of Cartesian graph products and bundles
• Approximation Algorithms and Hardness of the k -Route Cut Problem
• Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs
• Parameterized Algorithms
• The connectivity function of a graph
• Retracted article: ``On the survivable network design problem with mixed connectivity requirements

This page was built for publication: The complexity of mixed-connectivity