Finding large \(k\)-clubs in undirected graphs (Q488393)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Finding large k-clubs in undirected graphs |
scientific article; zbMATH DE number 6390432
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Finding large \(k\)-clubs in undirected graphs |
scientific article; zbMATH DE number 6390432 |
Statements
Finding large \(k\)-clubs in undirected graphs (English)
0 references
26 January 2015
0 references
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
branch and bound
0 references
\(k\)-club
0 references
\(k\)-neighbourhood
0 references
0 references
0.8948171138763428
0 references
0.886422872543335
0 references
0.8568658828735352
0 references
0.8091867566108704
0 references
0.8040777444839478
0 references
