Finding maximum subgraphs with relatively large vertex connectivity

DOI10.1016/j.ejor.2014.05.041zbMath1339.05407OpenAlexW1967224446MaRDI QIDQ297249

Alexander Veremyev, Eduardo L. Pasiliao, Oleg A. Prokopyev, Vladimir L. Boginski

Publication date: 24 June 2016

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

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

zbMATH Keywords

computational complexitymixed integer programmingvertex connectivity2-clubclique relaxations

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Mixed integer programming (90C11) Abstract computational complexity for mathematical programming problems (90C60) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (8)

Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments ⋮ Multivariate algorithmics for finding cohesive subnetworks ⋮ An effective branch-and-bound algorithm for the maximum \(s\)-bundle problem ⋮ On integer programming models for the maximum 2-club problem and its robust generalizations in sparse graphs ⋮ On robust clusters of minimum cardinality in networks ⋮ On exact solution approaches for the longest induced path problem ⋮ On the maximum small-world subgraph problem ⋮ Finding groups with maximum betweenness centrality

Uses Software

• Pajek
• Pajek datasets
• SparseMatrix
• XPRESS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
• A branch-and-bound approach for maximum quasi-cliques
• An efficient algorithm for solving pseudo clique enumeration problem
• k-connectivity in random undirected graphs
• Classifying molecular sequences using a linkage graph with their pairwise similarities
• Relaxing the uniformity and independence assumptions using the concept of fractal dimension
• On the maximum quasi-clique problem
• Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
• On clique relaxation models in network analysis
• Clique-detection models in computational biochemistry and genomics
• Novel approaches for analyzing biological networks
• The university of Florida sparse matrix collection
• Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
• Finding the Vertex Connectivity of Graphs
• Parallel Complexity of the Connected Subgraph Problem
• The Structure and Function of Complex Networks
• The Spectra of Random Graphs with Given Expected Degrees
• Robustness and Strong Attack Tolerance of Low-Diameter Networks
• Network Analysis

This page was built for publication: Finding maximum subgraphs with relatively large vertex connectivity