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:
Graph Modification Problems: A Modern Perspective Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Smaller Kernels for Several FPT Problems Based on Simple Observations

verfasst von : Wenjun Li, Shuai Hu

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 field of parameterized computation and theory, as a pre-processing technique of algorithms, kernelization has received considerable attention. In this paper, we study the kernelization algorithms for several fixed parameter tractable problems, including Co-Path Set, Path-Contractibility and Connected Dominating Set on \(G_7\) Graphs. For these three problems, based on simple observations, we give simple kernelization algorithms with kernel size of \(4k, 3k+4\) and \(O(k^2)\) respectively, which are smaller than the previous corresponding smallest kernels \(6k, 5k+3\), and \(O(k^3)\).

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 Approximation Algorithms for the Multilevel Facility Location Problem with Linear/Submodular Penalties
Nächstes Kapitel Parameterized Minimum Cost Partition of a Tree with Supply and Demand
Literatur
1.
Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) kernelization. In: FOCS 2009, pp. 629–638 (2009)
2.
Cheng, Y., Cai, Z., Goebel, R., Lin, G., Zhu, B.: The radiation hybrid map construction problem: recognition, hardness, and approximation algorithms (2008). (unpublished manuscript)
3.
Cox, D.R., Burmeister, M., Price, E.R., Kim, S., Myers, R.M.: Radiation hybrid mapping: a somatic cell genetic method for constructing high resolution maps of mammalian chromosomes. Science 250, 245–250 (1990)CrossRef
4.
Dawar, A., Kreutzer, S.: Domination problems in nowhere-dense classes. In: FSTTCS2009, pp. 157–168 (2009)
5.
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)CrossRef
6.
Feng, Q., Zhou, Q., Li, S.: Randomized parameterized algorithms for co-path set problem. In: Chen, J., Hopcroft, J.E., Wang, J. (eds.) FAW 2014. LNCS, vol. 8497, pp. 82–93. Springer, Heidelberg (2014) CrossRef
7.
8.
Fernau, H.: Parameterized algorithmics: a graph-theoretic approach. Habilitationsschrift, Universität Tübingen, Germany (2005)
9.
Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: SODA2010, pp. 503–510. SIAM, Philadelphia (2010)
10.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP Completeness. W.H. Freeman, New York (1979) MATH
11.
Golovach, P.A., Villanger, Y.: Parameterized complexity for domination problems on degenerate graphs. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol. 5344, pp. 195–205. Springer, Heidelberg (2008) CrossRef
12.
Gu, Q., Imani, N.: Connectivity is not a limit for kernelization: planar connected dominating set. In: López-Ortiz, A. (ed.) LATIN 2010. LNCS, vol. 6034, pp. 26–37. Springer, Heidelberg (2010) CrossRef
13.
Heggernes, P., Hof, P.V.T., Lokshtanov, D., Paul, C.: Obtaining a bipartite graph by contracting few edges. SIAM J. Discrete Math. 27(4), 2143–2156 (2013)MATHMathSciNetCrossRef
14.
Heggernes, P., Hof, P.V., Lokshtanov, D., Paul, C.: Contracting graphs to paths and trees. Algorithmica 68(1), 109–1320 (2014)MATHMathSciNetCrossRef
15.
Hermelin, D., Mnich, M., van Leeuwen, E.J., Woeginger, G.J.: Domination when the stars are out. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 462–473. Springer, Heidelberg (2011) CrossRef
16.
Jiang, H., Zhang, C., Zhu, B.: Weak kernels. ECCC Report, TR10-005 (2010)
17.
Lokshtanov, D., Mnich, M., Saurabh, S.: A linear kernel for a planar connected dominating set. Theor. Comput. Sci. 412(23), 2536–2543 (2011)MATHMathSciNetCrossRef
18.
Luo, W., Wang, J., Feng, Q., Guo, J., Chen, J.: An improved kernel for planar connected dominating set. In: Ogihara, M., Tarui, J. (eds.) TAMC 2011. LNCS, vol. 6648, pp. 70–81. Springer, Heidelberg (2011) CrossRef
19.
Marx, D.: Chordal deletion is fixed-parameter tractable. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol. 4271, pp. 37–48. Springer, Heidelberg (2006) CrossRef
20.
Misra, N., Philip, G., Raman, V., Saurabh, S.: The kernelization complexity of connected domination in graphs with (no) small cycles. Algorithmica 68(2), 504–530 (2014)MATHMathSciNetCrossRef
21.
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)MATHMathSciNetCrossRef
22.
Richard, C.W., Withers, D.A., Meeker, T.C., Maurer, S., Evans, G.A., Myers, R.M., Cox, D.R.: A radiation hybrid map of the proximal long arm of human chromosome 11 containing the multiple endocrine neoplasia type 1 (MEN-1) and bcl-1 disease loci. Am. J. Hum. Genet. 49(6), 1189 (1991)
23.
Slonim, D., Kruglyak, L., Stein, L., Lander, E.: Building human genome maps with radiation hybrids. J. Comput. Biol. 4, 487–504 (1997)CrossRef
24.
Zhang, C., Jiang, H., Zhu, B.: Radiation hybrid map construction problem parameterized. In: Lin, G. (ed.) COCOA 2012. LNCS, vol. 7402, pp. 127–137. Springer, Heidelberg (2012) CrossRef
Metadaten
Titel
Smaller Kernels for Several FPT Problems Based on Simple Observations
verfasst von
Wenjun Li
Shuai Hu
Copyright-Jahr
2015
Buch
Frontiers in Algorithmics

Print ISBN: 978-3-319-19646-6

Electronic ISBN: 978-3-319-19647-3

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-19647-3_16