Finding large \(k\)-clubs in undirected graphs (Q488393): Difference between revisions

A \(k\)-club is a maximal set of vertices of a graph that induces a subgraph of diameter \(k\). Related concepts are \(k\)-clique and \(k\)-clan, see \textit{J.-M. Bourjolly} et al. [Comput. Oper. Res. 27, No. 6, 559--569 (2000; Zbl 0955.91051); Eur. J. Oper. Res. 138, No. 1, 21--28 (2002; Zbl 1008.90048)]. This paper presents a branch-and-bound algorithm computing a maximum \(k\)-club in time \(O^\ast(1.62^n)\), and a heuristic for the same problem.

0 references

zbMATH Keywords

branch and bound

0 references

\(k\)-club

0 references

\(k\)-neighbourhood

0 references

describes a project that uses

DIMACS

0 references

MaRDI profile type

Publication

0 references

full work available at URL

https://doi.org/10.1007/s00607-012-0263-3

0 references

cites work

A graph‐theoretic definition of a sociometric clique†

0 references

Integer models and upper bounds for the 3‐club problem

0 references

Approximating Maximum Diameter-Bounded Subgraphs

0 references

Novel approaches for analyzing biological networks

0 references

Heuristics for finding \(k\)-clubs in an undirected graph

0 references

An exact algorithm for the maximum \(k\)-club problem in an undirected graph

0 references

Upper bounds and heuristics for the 2-club problem

0 references

A new approach to dynamic all pairs shortest paths

0 references

Q4745163

0 references

Graph Clustering and Minimum Cut Trees

0 references

A measure & conquer approach for the analysis of exact algorithms

0 references

Semi-dynamic shortest paths and breadth-first search in digraphs

0 references

Fully Dynamic Algorithms for Maintaining Shortest Paths Trees

0 references

Solving the maximum clique problem using a tabu search approach

0 references

Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs

0 references

Q3994557

0 references

On clusterings

0 references

Parameterized computational complexity of finding small-diameter subgraphs

0 references

On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs

0 references

Algorithms for the maximum \(k\)-club problem in graphs

0 references

Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems

0 references

Q4397004

0 references

Identifiers

zbMATH Open document ID

1310.05195

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

10.1007/S00607-012-0263-3

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:488393

@@ Property / DOI @@
-.1007/s00607-012-0263-3
@@ Property / DOI: 10.1007/s00607-012-0263-3 / rank @@
-Normal rank
@@ Property / review text @@
+A \(k\)-club is a maximal set of vertices of a graph that induces a subgraph of diameter \(k\). Related concepts are \(k\)-clique and \(k\)-clan, see \textit{J.-M. Bourjolly} et al. [Comput. Oper. Res. 27, No. 6, 559--569 (2000; Zbl 0955.91051); Eur. J. Oper. Res. 138, No. 1, 21--28 (2002; Zbl 1008.90048)]. This paper presents a branch-and-bound algorithm computing a maximum \(k\)-club in time \(O^\ast(1.62^n)\), and a heuristic for the same problem.
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C85
@@ Property / Mathematics Subject Classification ID: 05C85 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+R10
@@ Property / Mathematics Subject Classification ID: 68R10 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+B10
@@ Property / Mathematics Subject Classification ID: 90B10 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6390432
@@ Property / zbMATH DE Number: 6390432 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+branch and bound
@@ Property / zbMATH Keywords: branch and bound / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+\(k\)-club
@@ Property / zbMATH Keywords: \(k\)-club / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+\(k\)-neighbourhood
@@ Property / zbMATH Keywords: \(k\)-neighbourhood / rank @@
+Normal rank
@@ Property / describes a project that uses @@
+DIMACS
@@ Property / describes a project that uses: DIMACS / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+Publication
@@ Property / MaRDI profile type: Publication / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/s00607-012-0263-3
+Normal rank
@@ Property / OpenAlex ID @@
+W1988659376
@@ Property / OpenAlex ID: W1988659376 / rank @@
+Normal rank
@@ Property / cites work @@
+A graph‐theoretic definition of a sociometric clique†
+Normal rank
@@ Property / cites work @@
+Integer models and upper bounds for the 3‐club problem
+Normal rank
@@ Property / cites work @@
+Approximating Maximum Diameter-Bounded Subgraphs
@@ Property / cites work: Approximating Maximum Diameter-Bounded Subgraphs / rank @@
+Normal rank
@@ Property / cites work @@
+Novel approaches for analyzing biological networks
+Normal rank
@@ Property / cites work @@
+Heuristics for finding \(k\)-clubs in an undirected graph
+Normal rank
@@ Property / cites work @@
+An exact algorithm for the maximum \(k\)-club problem in an undirected graph
+Normal rank
@@ Property / cites work @@
+Upper bounds and heuristics for the 2-club problem
+Normal rank
@@ Property / cites work @@
+A new approach to dynamic all pairs shortest paths
+Normal rank
@@ Property / cites work @@
+Q4745163
@@ Property / cites work: Q4745163 / rank @@
+Normal rank
@@ Property / cites work @@
+Graph Clustering and Minimum Cut Trees
@@ Property / cites work: Graph Clustering and Minimum Cut Trees / rank @@
+Normal rank
@@ Property / cites work @@
+A measure &amp; conquer approach for the analysis of exact algorithms
+Normal rank
@@ Property / cites work @@
+Semi-dynamic shortest paths and breadth-first search in digraphs
+Normal rank
@@ Property / cites work @@
+Fully Dynamic Algorithms for Maintaining Shortest Paths Trees
+Normal rank
@@ Property / cites work @@
+Solving the maximum clique problem using a tabu search approach
+Normal rank
@@ Property / cites work @@
+Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs
+Normal rank
@@ Property / cites work @@
+Q3994557
@@ Property / cites work: Q3994557 / rank @@
+Normal rank
@@ Property / cites work @@
+On clusterings
@@ Property / cites work: On clusterings / rank @@
+Normal rank
@@ Property / cites work @@
+Parameterized computational complexity of finding small-diameter subgraphs
+Normal rank
@@ Property / cites work @@
+On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs
+Normal rank
@@ Property / cites work @@
+Algorithms for the maximum \(k\)-club problem in graphs
+Normal rank
@@ Property / cites work @@
+Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
+Normal rank
@@ Property / cites work @@
+Q4397004
@@ Property / cites work: Q4397004 / rank @@
+Normal rank
@@ Property / DOI @@
+.1007/S00607-012-0263-3
@@ Property / DOI: 10.1007/S00607-012-0263-3 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:488393