Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Algorithms for the Ring Star Problem Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

Planar Vertex-Disjoint Cycle Packing: New Structures and Improved Kernel

verfasst von : Qilong Feng, Xiaolu Liao, Jianxin Wang

Erschienen in: Combinatorial Optimization and Applications

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

The Maximum Cycle Packing problem is an important class of NP-hard problems, which has lots of applications in many fields. In this paper, we study Parameterized Planar Vertex-Disjoint Cycle Packing problem, which is to find k vertex-disjoint cycles in a given planar graph. The current best kernel size for this problem is \(1209k-1317\). Based on properties of maximal cycle packing, small cycles, degree-2 paths, and new reduction rules given, a kernel of size \(415k-814\) is presented for Parameterized Planar Vertex-Disjoint Cycle Packing problem.

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Modeling and Verifying Multi-core Programs
Nächstes Kapitel On the Linearization of Scaffolds Sharing Repeated Contigs
Literatur
1.
Bodlaender, H.L., Penninkx, E., Tan, R.B.: A linear kernel for the \(k\)-disjoint cycle problem on planar graphs. In: Proceedings of 19th International Symposium on Algorithms and Computation, pp. 306–317 (2008)
2.
Kloks, T., Lee, C.M., Liu, J.: New algorithms for \(k\)-face cover, \(k\)-feedback vertex set, and \(k\)-disjoint cycles on plane and planar graphs. In: Proceedings of 28th International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 282–295 (2002)
3.
Kakimura, N., Kawarabayashi, K., Marx, D.: Packing cycles through prescribed vertices. J. Comb. Theor. Ser. B 101(5), 378–381 (2011)CrossRefMATHMathSciNet
4.
Grohe, M., Grüber, M.: Parameterized approximability of the disjoint cycle problem. In: Proceedings of 34th International Colloquium on Automata, Languages and Programming, pp. 363–374 (2007)
5.
Bodlaender, H.L., Thomassé, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570–4578 (2011)CrossRefMATHMathSciNet
6.
Fellows, M., Heggernes, P., Rosamond, F., Sloper, C., Telle, J.A.: Finding \(k\) disjoint triangles in an arbitrary graph. In: Proceedings of 30th International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 235–244 (2004)
7.
Guo, J., Niedermeier, R.: Linear problem kernels for NP-Hard problems on planar graphs. In: Proceedings of 34th International Colloquium on Automata, Languages and Programming, pp. 375–386 (2007)
8.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., New York (1979)MATH
9.
Agrawal, A., Lokshtanov, D., Majumdar, D., Mouawad, A.E., Saurabh, S.: Kernelization of cycle packing with relaxed disjointness constraints. In: Proceedings of 43rd International Colloquium on Automata, Languages, and Programming, pp. 26:1–26:14 (2016)
10.
Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Preprocessing for treewidth: a combinatorial analysis through kernelization. SIAM J. Discret. Math. 27(4), 2108–2142 (2013)CrossRefMATHMathSciNet
Metadaten
Titel
Planar Vertex-Disjoint Cycle Packing: New Structures and Improved Kernel
verfasst von
Qilong Feng
Xiaolu Liao
Jianxin Wang
Copyright-Jahr
2017
Buch
Combinatorial Optimization and Applications

Print ISBN: 978-3-319-71146-1

Electronic ISBN: 978-3-319-71147-8

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-71147-8_37