Skip to main content

2012 | OriginalPaper | Buchkapitel

Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs

verfasst von : Sepp Hartung, Christian Komusiewicz, André Nichterlein

Erschienen in: Parameterized and Exact Computation

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Given an undirected graph

G

 = (

V

,

E

) and an integer ℓ ≥ 1, the NP-hard

2-Club

problem asks for a vertex set

S

 ⊆ 

V

of size at least ℓ 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 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 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

| − ℓ

) search tree algorithm [Schäfer et al., Optim. Lett. 2012] cannot be improved and that, unless NP ⊆ coNP/poly, there is no polynomial kernel for the dual parameter |

V

| − ℓ. Finally, we show that, in spite of this lower bound, the search tree algorithm for the dual parameter |

V

| − ℓ can be tuned into an efficient exact algorithm for

2-Club

that substantially outperforms previous implementations.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Metadaten
Titel
Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs
verfasst von
Sepp Hartung
Christian Komusiewicz
André Nichterlein
Copyright-Jahr
2012
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-642-33293-7_22