Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.01.2015 | Ausgabe 1/2015

Journal of Combinatorial Optimization 1/2015

Randomized parameterized algorithms for \(P_2\)-Packing and Co-Path Packing problems

Zeitschrift:
Journal of Combinatorial Optimization > Ausgabe 1/2015
Autoren:
Qilong Feng, Jianxin Wang, Shaohua Li, Jianer Chen
Wichtige Hinweise
A preliminary version of this work was reported in the Proceedings of the 19th Annual International Computing and Combinatorics Conference, Lecture Notes in Computer Science, vol. 7936, 2013, pp. 89–100.

Abstract

In this paper, we study the Parameterized \(P_2\)-Packing problem and Parameterized Co-Path Packing problem from random perspective. For the Parameterized \(P_2\)-Packing problem, based on the structure analysis of the problem and using random partition technique, a randomized parameterized algorithm of running time \(O^*(6.75^k)\) is obtained, improving the current best result \(O^*(8^k)\). For the Parameterized Co-Path Packing problem, we firstly study the kernel and randomized algorithm for the degree-bounded instance, where each vertex in the instance has degree at most three. A kernel of size \(20k\) and a randomized algorithm of running time \(O^*(2^k)\) are given for the Parameterized Co-Path Packing problem with bounded degree constraint. By applying iterative compression technique and based on the randomized algorithm for degree bounded problem, a randomized algorithm of running time \(O^*(3^k)\) is given for the Parameterized Co-Path Packing problem.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 1/2015

Journal of Combinatorial Optimization 1/2015 Zur Ausgabe

Premium Partner

    Bildnachweise