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:
Preliminaries Kapitel lesen Erstes Kapitel lesen

2013 | OriginalPaper | Buchkapitel

7. Further Elementary Techniques

verfasst von : Rodney G. Downey, Michael R. Fellows

Erschienen in: Fundamentals of Parameterized Complexity

Verlag: Springer London

Einloggen

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

search-config
loading …

Abstract

We explore a number of elementary techniques including the extremal method, greedy localization and bounded variable integer programming.

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 Iterative Compression, and Measure and Conquer, for Minimization Problems
Nächstes Kapitel Color Coding, Multilinear Detection, and Randomized Divide and Conquer
Fußnoten
1
We remark that the P-time extremal structure approach uncovers 14 more reduction rules, yielding a much tighter kernelization bound, but the argument is laborious and beyond the scope of this book. See [278].
 
Literatur
8.
F. Abu-Khzam, A quadratic kernel for 3-set packing, in Theory and Applications of Models of Computation, Proceedings of 6th Annual Conference, TAMC 2009, Changsha, China, May 18–22, 2009, ed. by J. Chen, B. Cooper. LNCS, vol. 5532 (Springer, Berlin, 2009), pp. 81–87
30.
N. Alon, Y. Azar, G. Woeginger, T. Yadid, Approximation schemes for scheduling on parallel machines. J. Sched. 1, 55–66 (1998) MathSciNetCrossRefMATH
140.
J. Chen, H. Fernau, I. Kanj, G. Xia, Parametric duality and kernelization: lower bounds and upper bounds on kernel size. SIAM J. Comput. 37(4), 1077–1106 (2007) MathSciNetCrossRefMATH
142.
J. Chen, D. Friesen, W. Jia, I. Kanj, Using nondeterminism to design efficient deterministic algorithms. Algorithmica 40(2), 83–97 (2004) MathSciNetCrossRefMATH
150.
J. Chen, Y. Liu, S. Lu, B. O’Sullivan, I. Razgon, A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55(5), 1–19 (2008) MathSciNet
203.
F. Dehne, M. Fellows, H. Fernau, E. Prieto, F. Rosamond, Nonblocker: parameterized algorithmics for minimum dominating set, in Proceedings of the 32nd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM ’06) (Springer, Berlin, 2006), pp. 237–245
204.
F. Dehne, M. Fellows, F. Rosamond, P. Shaw, Greedy localization, iterative compression, and modeled crown reductions: new FPT techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover, in Parameterized and Exact Computation, Proceedings of First International Workshop, IWPEC 2004, Bergen, Norway, September 14–17, 2004, ed. by R. Downey, M. Fellows, F. Dehne. LNCS, vol. 3162 (Springer, Berlin, 2004), pp. 271–281
278.
V. Estivill-Castro, M. Fellows, M. Langston, F. Rosamond, FPT is P-time extremal structure I, in Algorithms and Complexity in Durham 2005, Proceedings of the First ACiD Workshop. Texts in Algorithmics, vol. 4 (King’s College, Dusham, 2005), pp. 1–41
287.
M.R. Fellows, S. Gaspers, F.A. Rosamond, Parameterizing by the number of numbers. Theory Comput. Syst. 50(4), 675–693 (2012) MathSciNetCrossRefMATH
288.
M. Fellows, P. Heggernes, F. Rosamond, C. Sloper, J. Telle, Finding k disjoint triangles in an arbitrary graph, in Graph-Theoretic Concepts in Computer Science. LNCS, vol. 3353 (Springer, Berlin, 2004), pp. 235–244 CrossRef
289.
M. Fellows, P. Heggernes, F. Rosamond, C. Sloper, J.A. Telle, Exact algorithms for finding k disjoint triangles in an arbitrary graph, in Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Revised Papers, Bad Honnef, Germany, June 2004, ed. by J. Hromkovič, M. Nagl, B. Westfechtel. LNCS, vol. 3353 (Springer, Berlin, 2004), pp. 235–244 CrossRef
292.
M. Fellows, C. Knauer, N. Nishimura, P. Ragde, F. Rosamond, U. Stege, D. Thilikos, S. Whitesides, Faster fixed-parameter tractable algorithms for matching and packing problems. Algorithmica 52(2), 167–176 (2008) MathSciNetCrossRefMATH
350.
P. Golovach, D. Thilikos, Paths of bounded length and their cuts: parameterized complexity and algorithms. Discrete Optim. 8(1), 72–86 (2011) MathSciNetCrossRefMATH
357.
J. Gramm, R. Niedermeier, P. Rossmanith, Fixed-parameter algorithms for closest string and related problems. Algorithmica 37, 25–42 (2003) MathSciNetCrossRefMATH
416.
429.
449.
487.
518.
L. Mathieson, E. Prieto, P. Shaw, Packing edge disjoint triangles: a parameterized view, in Parameterized and Exact Computation, Proceedings of First International Workshop, IWPEC ’04, Bergen, Norway, September 2004, ed. by R. Downey, M. Fellows, F. Dehne. LNCS, vol. 3162 (Springer, Berlin, 2004), pp. 127–137 CrossRef
546.
R. Niedermeier, Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications, vol. 31 (Oxford University Press, Oxford, 2006) CrossRef
564.
E. Prieto, Systematic kernelization in FPT algorithm design, PhD thesis, School of Electrical Engineering and Computer Science, University of Newcastle, Australia, 2004
565.
E. Prieto, C. Sloper, Looking at the stars, in Parameterized and Exact Computation, Proceedings of First International Workshop, IWPEC ’04, Bergen, Norway, September 2004, ed. by R. Downey, M. Fellows, F. Dehne. LNCS, vol. 3162 (Springer, Berlin, 2004), pp. 138–148 CrossRef
624.
C. Sloper, J.A. Telle, Techniques for designing parameterized algorithms. Comput. J. 51(1), 122–136 (2008) CrossRef
Metadaten
Titel
Further Elementary Techniques
verfasst von
Rodney G. Downey
Michael R. Fellows
Copyright-Jahr
2013
Verlag
Springer London
Buch
Fundamentals of Parameterized Complexity

Print ISBN: 978-1-4471-5558-4

Electronic ISBN: 978-1-4471-5559-1

Copyright-Jahr: 2013

DOI
https://doi.org/10.1007/978-1-4471-5559-1_7