Geodesic
Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs
Journal of Graph Algorithms and Applications, Tome 19 (2015) no. 1, pp. 155-190.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

Given an undirected graph G=(V,E) and an integer l ≥ 1, the NP-hard 2-CLUB problem asks for a vertex set S ⊆ V of size at least l such that the subgraph induced by S has diameter at most two. In this work, we extend previous parameterized complexity studies for 2-CLUB. On the positive side, we give polynomial-size problem kernels for the parameters feedback edge set size of G and size of a cluster editing set of G and present a direct combinatorial algorithm for the parameter treewidth of G. On the negative side, we first show that unless NP ⊆ coNP/poly, 2-CLUB does not admit a polynomial-size problem kernel with respect to the size of a vertex cover of G. Next, we show that, under the strong exponential time hypothesis, a previous O(2|V|−l·|V||E|)-time search tree algorithm [Schäfer et al., Optim. Lett. 2012] cannot be improved and that, unless NP ⊆ coNP/poly, there is no polynomial-size problem kernel for the dual parameter |V|−l. Finally, we show that, in spite of this lower bound, the search tree algorithm for the dual parameter |V|−l can be tuned into an efficient exact algorithm for 2-CLUB that outperforms previous implementations.
DOI : 10.7155/jgaa.00352
Keywords: clique relaxation, network analysis, branch and bound, kernelization 
@article{JGAA_2015_19_1_a6,
     author = {Sepp Hartung and Christian Komusiewicz and Andr\'e Nichterlein},
     title = {Parameterized {Algorithmics} and {Computational} {Experiments} for {Finding} {2-Clubs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {155--190},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2015},
     doi = {10.7155/jgaa.00352},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00352/}
}
TY  - JOUR
AU  - Sepp Hartung
AU  - Christian Komusiewicz
AU  - André Nichterlein
TI  - Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs
JO  - Journal of Graph Algorithms and Applications
PY  - 2015
SP  - 155
EP  - 190
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00352/
DO  - 10.7155/jgaa.00352
LA  - en
ID  - JGAA_2015_19_1_a6
ER  - 
%0 Journal Article
%A Sepp Hartung
%A Christian Komusiewicz
%A André Nichterlein
%T Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs
%J Journal of Graph Algorithms and Applications
%D 2015
%P 155-190
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00352/
%R 10.7155/jgaa.00352
%G en
%F JGAA_2015_19_1_a6
Sepp Hartung; Christian Komusiewicz; André Nichterlein. Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs. Journal of Graph Algorithms and Applications, Tome 19 (2015) no. 1, pp. 155-190. doi : 10.7155/jgaa.00352. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00352/

Cité par Sources :