Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments

DOI10.1016/j.ejor.2018.12.006zbMath1430.05119arXiv1807.07516OpenAlexW2883786747WikidataQ128701273 ScholiaQ128701273MaRDI QIDQ1719617

Rolf Niedermeier, André Nichterlein, Marten Picker, Christian Komusiewicz

Publication date: 11 February 2019

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

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

zbMATH Keywords

combinatorial optimizationcommunity detectionfixed-parameter tractabilitygraph miningsmall-diameter subgraphs

Mathematics Subject Classification ID

Applications of graph theory (05C90) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09)

Related Items

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 ⋮ On 2-clubs in graph-based data clustering: theory and algorithm engineering ⋮ Graph Motif Problems Parameterized by Dual ⋮ 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

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding maximum subgraphs with relatively large vertex connectivity
• Fundamentals of parameterized complexity
• Finding clubs in graph classes
• Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
• On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs
• Finding large \(k\)-clubs in undirected graphs
• On robust clusters of minimum cardinality in networks
• Upper bounds and heuristics for the 2-club problem
• An exact algorithm for the maximum \(k\)-club problem in an undirected graph
• Which problems have strongly exponential complexity?
• Optimal approximation algorithms for maximum distance-bounded subgraph problems
• On biconnected and fragile subgraphs of low diameter
• Multivariate algorithmics for finding cohesive subnetworks
• Parameterized computational complexity of finding small-diameter subgraphs
• Heuristics for finding \(k\)-clubs in an undirected graph
• On clique relaxation models in network analysis
• An analytical comparison of the LP relaxations of integer models for the \(k\)-club problem
• Managing and mining graph data
• On structural parameterizations for the 2-club problem
• The triangle \(k\)-club problem
• Solving the maximum clique problem using a tabu search approach
• Parametrized complexity theory.
• Novel approaches for analyzing biological networks
• Maximal Flow Through a Network
• Finding the Vertex Connectivity of Graphs
• Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs
• Parameterized Algorithms