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 Queryable Uncertainty Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Kernelization of Two Path Searching Problems on Split Graphs

verfasst von : Yongjie Yang, Yash Raj Shrestha, Wenjun Li, Jiong Guo

Erschienen in: Frontiers in Algorithmics

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

In the k-Vertex-Disjoint Paths problem, we are given a graph G and k terminal pairs of vertices, and are asked whether there is a set of k vertex-disjoint paths linking these terminal pairs, respectively. In the k-Path problem, we are given a graph and are asked whether there is a path of length k. It is known that both problems are NP-hard even in split graphs, which are the graphs whose vertices can be partitioned into a clique and an independent set. We study kernelization for the two problems in split graphs. In particular, we derive a 4k vertex-kernel for the k-Vertex-Disjoint Paths problem and a \(\frac{3}{2}k^2+\frac{1}{2}k\) vertex-kernel for the k-Path 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 A PTAS for the Multiple Parallel Identical Multi-stage Flow-Shops to Minimize the Makespan
Nächstes Kapitel The Bounded Batch Scheduling with Common Due Window and Non-identical Size Jobs
Literatur
1.
2.
Abu-Khzam, F.N., Fellows, M.R., Langston, M.A., Suters, W.H.: Crown structures for vertex cover kernelization. Theor. Comput. Syst. 41(3), 411–430 (2007)MathSciNetCrossRefMATH
3.
Adcock, A.B., Demaine, E.D., Demaine, M.L., O’Brien, M.P., Reidl, F., Villaamil, F.S., Sullivan, B.D.: Zig-zag numberlink is NP-complete. JIP 23(3), 239–245 (2015)
4.
Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423–434 (2009)MathSciNetCrossRefMATH
5.
Bodlaender, H.L., Thomassé, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570–4578 (2011)MathSciNetCrossRefMATH
6.
Chor, B., Fellows, M., Juedes, D.W.: Linear kernels in linear time, or how to save k colors in \(O(n^2)\) steps. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 257–269. Springer, Heidelberg (2004)CrossRef
7.
Frank, A.: Packing paths, circuits and cuts: a survey. In: Korte, B., Lovász, L., Prömel, H.J., Schrijver, A. (eds.) Paths, Flows, and VLSI-Layout, pp. 49–100. Springer, Berlin (1990)
8.
Heggernes, P., Hof, P., van Leeuwen, E.J., Saei, R.: Finding disjoint paths in split graphs. Theor. Comput. Syst. 57(1), 140–159 (2015)MathSciNetCrossRefMATH
9.
Heggernes, P., Lokshtanov, D., Mihai, R., Papadopoulos, C.: Cutwidth of split graphs and threshold graphs. SIAM J. Discrete Math. 25(3), 1418–1437 (2011)MathSciNetCrossRefMATH
10.
Jansen, B.M.P.: Turing kernelization for finding long paths and cycles in restricted graph classes. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 579–591. Springer, Heidelberg (2014)
11.
Karp, R.M., Leighton, F.T., Rivest, R.L., Thompson, C.D., Vazirani, U.V., Vazirani, V.V.: Global wire routing in two-dimensional arrays. Algorithmica 2, 113–129 (1987)MathSciNetCrossRefMATH
12.
Kramer, M.R., van Leeuwen, J.: The complexity of wire-routing and finding minimum area layouts for arbitrary VLSI circuits. Adv. Comput. Res. 2, 129–146 (1984)
13.
Lynch, J.F.: The equivalence of theorem proving and the interconnection problem. SIGDA Newsl. 5(3), 31–36 (1975)CrossRef
14.
15.
16.
Natarajan, S., Sprague, A.P.: Disjoint paths in circular arc graphs. Nord. J. Comput. 3(3), 256–270 (1996)MathSciNet
17.
Prieto, E., Sloper, C.: Looking at the stars. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol. 3162, pp. 138–148. Springer, Heidelberg (2004)CrossRef
18.
Raman, V., Saurabh, S.: Short cycles make W-hard problems hard: FPT algorithms for W-hard problems in graphs with no short cycles. Algorithmica 52(2), 203–225 (2008)MathSciNetCrossRefMATH
19.
Robertson, N., Seymour, P.D.: An outline of a disjoint path algorithm. In: Korte, B., Lovász, L., Prömel, H.J., Schrijver, A. (eds.) Paths, Flows, and VLSI-Layout, pp. 267–292. Springer, Berlin (1990)
20.
21.
Wang, J., Yang, Y., Guo, J., Chen, J.: Planar graph vertex partition for linear problem kernels. J. Comput. Syst. Sci. 79(5), 609–621 (2013)MathSciNetCrossRefMATH
22.
Metadaten
Titel
Kernelization of Two Path Searching Problems on Split Graphs
verfasst von
Yongjie Yang
Yash Raj Shrestha
Wenjun Li
Jiong Guo
Copyright-Jahr
2016
Buch
Frontiers in Algorithmics

Print ISBN: 978-3-319-39816-7

Electronic ISBN: 978-3-319-39817-4

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-39817-4_23

Premium Partner

    Bildnachweise