Finding large \(k\)-clubs in undirected graphs

DOI10.1007/S00607-012-0263-3zbMath1310.05195OpenAlexW1988659376MaRDI QIDQ488393

Ling-Ju Hung, Ping-Chen Su, Chih-Ren Lin, Maw-Shang Chang

Publication date: 26 January 2015

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00607-012-0263-3

zbMATH Keywords

branch and bound\(k\)-club\(k\)-neighbourhood

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (21)

Optimal approximation algorithms for maximum distance-bounded subgraph problems ⋮ Identifying risk-averse low-diameter clusters in graphs with stochastic vertex weights ⋮ Finding disjoint dense clubs in a social network ⋮ On Fault-Tolerant Low-Diameter Clusters in Graphs ⋮ Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems ⋮ The parameterized complexity of \(s\)-club with triangle and seed constraints ⋮ Approximating maximum diameter-bounded subgraph in unit disk graphs ⋮ On the tractability of finding disjoint clubs in a network ⋮ Computing dense and sparse subgraphs of weakly closed graphs ⋮ On the 2-Club Polytope of Graphs ⋮ Covering a Graph with Clubs ⋮ Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments ⋮ Finding Disjoint Dense Clubs in an Undirected Graph ⋮ Multivariate algorithmics for finding cohesive subnetworks ⋮ The parameterized complexity of \(s\)-club with triangle and seed constraints ⋮ A hybrid artificial immune network for detecting communities in complex networks ⋮ Efficient branch-and-bound algorithms for finding triangle-constrained 2-clubs ⋮ On the tractability of covering a graph with 2-clubs ⋮ Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs ⋮ On structural parameterizations for the 2-club problem ⋮ Algorithms and complexity of \(s\)-club cluster vertex deletion

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• 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
• An exact algorithm for the maximum \(k\)-club problem in an undirected graph
• Parameterized computational complexity of finding small-diameter subgraphs
• Heuristics for finding \(k\)-clubs in an undirected graph
• Solving the maximum clique problem using a tabu search approach
• Novel approaches for analyzing biological networks
• A measure & conquer approach for the analysis of exact algorithms
• Approximating Maximum Diameter-Bounded Subgraphs
• On clusterings
• A graph‐theoretic definition of a sociometric clique†
• Graph Clustering and Minimum Cut Trees
• Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs
• Fully Dynamic Algorithms for Maintaining Shortest Paths Trees
• Semi-dynamic shortest paths and breadth-first search in digraphs
• Integer models and upper bounds for the 3‐club problem
• A new approach to dynamic all pairs shortest paths

This page was built for publication: Finding large \(k\)-clubs in undirected graphs