On biconnected and fragile subgraphs of low diameter

DOI10.1016/j.ejor.2017.05.020zbMath1380.05169OpenAlexW2615011235MaRDI QIDQ1694912

Foad Mahdavi Pajouh, Oleksandra Yezerska, Sergiy I. Butenko

Publication date: 6 February 2018

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2017.05.020

zbMATH Keywords

branch-and-cutrobust network clusterscombinatorial branch-and-bound2-clubsbiconnected 2-clubsfragile 2-clubs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Structural characterization of families of graphs (05C75)

Related Items (8)

Minimum cost edge blocker clique problem ⋮ On Fault-Tolerant Low-Diameter Clusters in Graphs ⋮ The parameterized complexity of \(s\)-club with triangle and seed constraints ⋮ On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering ⋮ Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments ⋮ On integer programming models for the maximum 2-club problem and its robust generalizations in sparse graphs ⋮ The parameterized complexity of \(s\)-club with triangle and seed constraints ⋮ On the maximum small-world subgraph problem

Uses Software

• Gurobi
• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Algorithms for the maximum \(k\)-club problem in graphs
• Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
• On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs
• Upper bounds and heuristics for the 2-club problem
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Variable neighborhood search
• An exact algorithm for the maximum \(k\)-club problem in an undirected graph
• Finding a maximum \(k\)-club using the \(k\)-clique formulation and canonical hypercube cuts
• Heuristics for finding \(k\)-clubs in an undirected graph
• On clique relaxation models in network analysis
• Solving the maximum clique problem using a tabu search approach
• Novel approaches for analyzing biological networks
• Distance-Based Clique Relaxations in Networks: s-Clique and s-Club
• On the 2-Club Polytope of Graphs
• New methods to color the vertices of a graph
• On provably best construction heuristics for hard combinatorial optimization problems
• Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs
• Integer models and upper bounds for the 3‐club problem
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: On biconnected and fragile subgraphs of low diameter