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

29. The M-Hierarchy, and XP-Optimality

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 relate NP to parameterized complexity via the ETH, SETH, and prove results on XP-optimality. Namely, we give methods to show that, under reasonable hypotheses, current algorithms for various computational tasks are optimal up to an O-factor.

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 Another Basis for the W-Hierarchy and the Tradeoff Theorem
Nächstes Kapitel Kernelization Lower Bounds
Fußnoten
1
Known to the authors as “son of feasible” as reported in Downey [237].
 
2
Many of the key ideas in this were implicit, in some sense, in [126, 127], we are following the route of Downey et al. [238] which contained the definition of Mini-W[1] and of miniatures of NP problems, many combinatorial reductions, especially Theorem 29.4.2, the Turing counting trick, and the inclusion of Mini[1] in W[1]. The programme was initiated by Cai and Juedes [127].
 
3
The reader may note that there are in effect three theorems being proven here, depending on the level of uniformity in the notion of M[1]. This is kind of important below when we prove lower bounds. For the strongest results, we will be assuming the nonuniform version that M[1]∉ nonuniform FPT.
 
4
This neat proof is an unpublished one due to Yijia Chen.
 
5
To distinguish this from k-Hitting Set.
 
6
Here definitely note that if we do not assume more than the existence of an algorithm, then f may not be computable, and hence we will need the nonuniform version of ETH.
 
7
According to [361], this can be done in O(n 3) steps (the result in [361] is an improvement of the algorithm of Seymour and Thomas in [615]).
 
8
Formally, the contraction relation occurs if in the definition of the minor relation we additionally demand that
(c)
for every {x,y}∈E(G), either φ(x)=φ(y) or {φ(x),φ(y)}∈E(H).
 
 
Literatur
2.
K. Abrahamson, R. Downey, M. Fellows, Fixed-parameter intractability II, in Proceedings of 10th Annual Symposium on Theoretical Aspects on Computer Science, STACS 93, Würzburg, Germany, February 25–27, 1993, ed. by P. Enjalbert, A. Finkel, K. Wagner. LNCS, vol. 665 (Springer, Berlin, 1993), pp. 374–385
3.
K. Abrahamson, R. Downey, M. Fellows, Fixed-parameter tractability and completeness. IV. On completeness for W[P] and PSPACE analogues. Ann. Pure Appl. Log. 73(3), 235–276 (1995) MathSciNetCrossRefMATH
6.
K. Abrahamson, M. Fellows, J. Ellis, M. Mata, On the complexity of fixed parameter problems, in Proceedings of 30th Annual Symposium on Foundations of Computer Science, FOCS 1989, Research Triangle Park, North Carolina, USA, 30 October–1 November 1989 (IEEE Comput. Soc., Los Alamitos, 1989), pp. 210–215
21.
J. Alber, H. Bodlaender, H. Fernau, T. Kloks, R. Niedermeier, Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica 33(4), 461–493 (2002) MathSciNetCrossRefMATH
22.
J. Alber, H. Bodlaender, H. Fernau, R. Niedermeier, Fixed parameter algorithms for planar dominating set and related problems, in Algorithm Theory—SWAT 2000, Proceedings of 7th Scandinavian Workshop on Algorithm Theory, Bergen, Norway, July 2000, ed. by M. Halldórsson. LNCS, vol. 1851 (Springer, London, 2000), pp. 97–110
35.
N. Alon, D. Lokshtanov, S. Saurabh, Fast FAST, in Proceedings of 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), Part I, Rhodes, Greece, July 5–12, 2009, ed. by S. Albers, A. Marchetti-Spaccamela, Y. Matias, S. Nikoletseas, W. Thomas. LNCS, vol. 5555 (Springer, Berlin, 2009), pp. 49–58 CrossRef
38.
S. Alstrup, P. Lauridsen, M. Thorup, Generalized dominators for structured programs, in Proceedings of the Third International Symposium on Static Analysis (SAS ’96), Aachen, Germany, September 24–26, 1996, ed. by R. Cousot, D. Schmidt. LNCS, vol. 1145 (Springer, Berlin, 1996), pp. 42–51
50.
115.
120.
L. Cai, J. Chen, On the amount of nondeterminism and the power of verifying, in Mathematical Foundations of Computer Science 1993, Proceedings of 18th International Symposium, MFCS ’93, Gdansk, Poland, August 30–September 3, 1993, ed. by A. Borzyszkowski, S. Sokolowski. LNCS, vol. 711 (Springer, Berlin, 1993), pp. 311–320 CrossRef
121.
L. Cai, J. Chen, On fixed-parameter tractability and approximability of NP optimization problems. J. Comput. Syst. Sci. 54(3), 465–474 (1997) MathSciNetCrossRefMATH
126.
L. Cai, D. Juedes, Subexponential parameterized algorithms collapse the W-hierarchy, in Proceedings of 28th International Colloquium on Automata, Languages and Programming (ICALP 2001), Crete, Greece, July 8–12, 2001, ed. by F. Orejas, P. Spirakis, J. van Leeuwen. LNCS, vol. 2076 (Springer, Berlin, 2001), pp. 273–284 CrossRef
127.
L. Cai, D. Juedes, On the existence of subexponential parameterized algorithms. J. Comput. Syst. Sci. 67(4), 789–807 (2003) MathSciNetCrossRefMATH
139.
J. Chen, B. Chor, M. Fellows, X. Huang, D. Juedes, I. Kanj, G. Xia, Tight lower bounds for certain parameterized NP-hard problems. Inf. Comput. 201, 216–231 (2005) MathSciNetCrossRefMATH
143.
J. Chen, X. Huang, I. Kanj, G. Xia, On the computational hardness based on linear FPT-reductions. J. Comb. Optim. 11(2), 231–247 (2006) MathSciNetCrossRefMATH
144.
J. Chen, X. Huang, I. Kanj, G. Xia, Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci. 72(8), 1346–1367 (2006) MathSciNetCrossRefMATH
147.
J. Chen, I. Kanj, L. Perkovic, E. Sedgwick, G. Xia, Genus characterizes the complexity of graph problems: some tight results, in Proceedings of 30th International Colloquium on Automata, Languages and Programming (ICALP 2003), Eindhoven, The Netherlands, June 30–July 4, 2003, ed. by J. Baeten, J.K. Lenstra, J. Parrow, G. Woeginger. LNCS, vol. 2719 (Springer, Berlin, 2003), pp. 845–856 CrossRef
155.
Y. Chen, M. Grohe, An isomorphism between subexponential and parameterized complexity theory. SIAM J. Comput. 37, 1228–1258 (2007) MathSciNetCrossRefMATH
164.
165.
186.
M. Cygan, H. Dell, D. Lokshtanov, D. Marx, J. Nederlof, Y. Okamoto, R. Paturi, S. Saurabh, M. Wahlström, On problems as hard as CNFSat, arXiv:​1112.​2275. To appear in CCC 2012
190.
M. Cygan, J. Nederlof, M. Pilipczuk, M. Pilipczuk, J. van Rooij, J.O. Wojtaszczyk, Solving connectivity problems parameterized by treewidth in single exponential time, in IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22–25, 2011, ed. by R. Ostrovsky (IEEE Comput. Soc., Los Alamitos, 2011)
207.
E. Demaine, F. Fomin, M. Hajiaghayi, D. Thilikos, Bidimensional parameters and local treewidth. SIAM J. Discrete Math. 18(3), 501–511 (2005) MathSciNetCrossRef
208.
E. Demaine, F. Fomin, M. Hajiaghayi, D. Thilikos, Fixed-parameter algorithms for (k,r)-center in planar graphs and map graphs. ACM Trans. Algorithms 1(1), 33–47 (2005) MathSciNetCrossRef
209.
E. Demaine, F. Fomin, M. Hajiaghayi, D. Thilikos, Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM 52(6), 866–893 (2005) MathSciNet
211.
E. Demaine, M. Hajiaghayi, Bidimensionality: new connections between FPT algorithms and PTASs, in Proceedings of the Sixteenth Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23–25, 2005 (SIAM, Philadelphia, 2005), pp. 590–601
212.
E. Demaine, M. Hajiaghayi, Bidimensionality, in Encyclopedia of Algorithms, ed. by M.-Y. Kao (Springer, Berlin, 2008), pp. 88–90 CrossRef
214.
E. Demaine, M. Hajiaghayi, Linearity of grid minors in treewidth with applications through bidimensionality. Combinatorica 28(1), 19–36 (2008) MathSciNetCrossRefMATH
217.
E. Demaine, M. Hajiaghayi, D. Thilikos, Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors. Algorithmica 41, 245–267 (2005) MathSciNetCrossRefMATH
218.
E. Demaine, M. Hajiaghayi, D. Thilikos, The bidimensional theory of bounded-genus graphs. SIAM J. Discrete Math. 20(2), 357–371 (2006) MathSciNetCrossRefMATH
230.
F. Dorn, Designing subexponential algorithms: problems, techniques and structures, PhD thesis, University of Bergen, July 2007
231.
F. Dorn, F. Fomin, D. Lokshtanov, V. Raman, S. Saurabh, Beyond bidimensionality: parameterized subexponential algorithms on directed graphs, in Proceedings of 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, Nancy, France, March 4–6, 2010, ed. by J.-Y. Marion, T. Schwentick. Leibniz International Proceedings in Informatics, vol. 5 (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, 2010), pp. 251–262
233.
F. Dorn, F. Fomin, D. Thilikos, Catalan structures and dynamic programming in H-minor-free graphs, in Proceedings of the Nineteenth Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20–22, 2008, ed. by S.-H. Teng (SIAM, Philadelphia, 2008), pp. 631–640
234.
F. Dorn, F.V. Fomin, D.M. Thilikos, Subexponential parameterized algorithms. Comput. Sci. Rev. 2(1), 29–39 (2008) CrossRef
235.
F. Dorn, E. Penninkx, H. Bodlaender, F. Fomin, Efficient exact algorithms on planar graphs: exploiting sphere cut decompositions. Algorithmica 58(3), 790–810 (2010) MathSciNetCrossRefMATH
237.
R. Downey, The birth and early years of parameterized complexity, in The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, ed. by H. Bodlaender, R. Downey, F. Fomin, D. Marx. LNCS, vol. 7370 (Springer, Berlin, 2012), pp. 17–38 CrossRef
238.
R. Downey, V. Estivill-Castro, M. Fellows, E. Prieto, F. Rosamond, Cutting up is hard to do: the parameterised complexity of k-cut and related problems, in Computing: the Australasian Theory Symposium, CATS 2003. Electronic Notes in Theoretical Computer Science, vol. 78 (Elsevier, Amsterdam, 2003), pp. 209–222
247.
R. Downey, M. Fellows, Parameterized Complexity. Monographs in Computer Science (Springer, Berlin, 1999) CrossRef
257.
R. Downey, M. Fellows, U. Stege, Parameterized complexity: a framework for systematically confronting computational intractability, in Contemporary Trends in Discrete Mathematics: from DIMACS and DIMATIA to the Future, DIMATIA-DIMACS Conference, Štiřín Castle, May 19–25, 1997, ed. by R. Grahm, J. Kratochvíl, J. Nesetril, F. Roberts. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 49 (Am. Math. Soc., Providence, 1999), pp. 49–100
261.
R. Downey, D. Thilikos, Confronting intractability via parameters. Comput. Sci. Rev. 5(4), 279–317 (2011) CrossRef
286.
M. Fellows, F. Fomin, D. Lokshtanov, F. Rosamond, S. Saurabh, S. Szeider, C. Thomassen, On the complexity of some colorful problems parameterized by treewidth. Inf. Comput. 209(2), 143–153 (2011) MathSciNetCrossRefMATH
305.
H. Fernau, Graph separator algorithms: a refined analysis, in Graph-Theoretic Concepts in Computer Science: 28th International Workshop, WG 2002, Revised Papers, Ceský Krumlov, Czech Republic, June 2002, ed. by L. Kućera. LNCS, vol. 2573 (Springer, Berlin, 2002), pp. 186–197 CrossRef
307.
H. Fernau, D. Juedes, A geometric approach to parameterized algorithms for domination problems on planar graphs, in Mathematical Foundations of Computer Science 2004, Proceedings of 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22–27, 2004, ed. by J. Fiala, V. Koubek, J. Kratochvíl. LNCS, vol. 3153 (Springer, Berlin, 2004), pp. 488–499
311.
J. Flum, M. Grohe, Parameterized complexity and subexponential time. Bull. Eur. Assoc. Theor. Comput. Sci. 84, 71–100 (2004) MathSciNetMATH
313.
J. Flum, M. Grohe, M. Weyer, Bounded fixed-parameter tractability and log2 n nondeterministic bits. J. Comput. Syst. Sci. 72(1), 34–71 (2006) MathSciNetCrossRefMATH
315.
F. Fomin, P. Golovach, D. Thilikos, Contraction bidimensionality: the accurate picture, in Algorithms—ESA 2009: Proceedings of 17th Annual European Symposium, Copenhagen, Denmark, September 7–9, 2009, ed. by A. Fiat, P. Sanders. LNCS, vol. 5757 (Springer, Berlin, 2009), pp. 706–717 CrossRef
322.
F. Fomin, D. Lokshtanov, V. Raman, S. Saurabh, Bidimensionality and EPTAS, in Proceedings of the Twenty-Second Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23–25, 2011, ed. by D. Randall (SIAM, Philadelphia, 2011), pp. 748–759
323.
F. Fomin, D. Lokshtanov, S. Saurabh, Kernelization: Theory of Parameterized Compressibility (Cambridge University Press, Cambridge, to appear)
324.
F. Fomin, D. Lokshtanov, S. Saurabh, D. Thilikos, Bidimensionality and kernels, in Proceedings of the Twenty-First Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17–19, 2010, ed. by M. Charikar (SIAM, Philadelphia, 2010), pp. 503–510
325.
F. Fomin, D. Thilikos, Dominating sets in planar graphs: branch-width and exponential speed-up. SIAM J. Comput. 36(2), 281–309 (2006) MathSciNetCrossRefMATH
326.
F. Fomin, Y. Villanger, Subexponential parameterized algorithm for minimum fill-in, in Proceedings of the Twenty-Third Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012, ed. by Y. Rabani (SIAM, Philadelphia, 2012), pp. 1737–1746
339.
344.
J. Geske, On the structure of intractable sets (binary relation), PhD thesis, Iowa State University, Ames, Iowa, USA, 1987
357.
J. Gramm, R. Niedermeier, P. Rossmanith, Fixed-parameter algorithms for closest string and related problems. Algorithmica 37, 25–42 (2003) MathSciNetCrossRefMATH
361.
Q.-P. Gu, H. Tamaki, Optimal branch decomposition of planar graphs in O(n 3) time. ACM Trans. Algorithms 4(3), 1–13 (2008) MathSciNetCrossRef
362.
Q.-P. Gu, H. Tamaki, Improved bounds on the planar branchwidth with respect to the largest grid minor size, in Algorithms and Computation: Proceedings of 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15–17, 2010, ed. by O. Cheong, K.-Y. Chwa, K. Park. LNCS, vol. 6507 (Springer, Berlin, 2010), pp. 85–96 CrossRef
368.
Y. Gurevich, S. Shelah, Nearly linear time, in Logic at Botik ’89: Symposium on Logical Foundations of Computer Science, ed. by A. Meyer, M. Taitslin. LNCS, vol. 363 (Springer, Berlin, 1989), pp. 108–118 CrossRef
410.
R. Impagliazzo, R. Paturi, The complexity of k-sat, in Proceedings of the 14th Annual IEEE Conference on Computational Complexity, CCC 1999, Atlanta, GA, USA, May 4–6, 1999 (IEEE Comput. Soc., Los Alamitos, 1999), pp. 237–240
411.
R. Impagliazzo, R. Paturi, F. Zane, Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512–530 (2001) MathSciNetCrossRefMATH
423.
D. Joseph, R. Pruim, P. Young, Collapsing degrees in subexponential time, in Proceedings of Ninth Annual Structure in Complexity Theory Conference, University of Wisconsin, Madison, Wisconsin, June 28–July 1, 1994 (IEEE Comput. Soc., Los Alamitos, 1994), pp. 367–382 CrossRef
428.
I. Kanj, L. Perković, Improved parameterized algorithms for planar dominating set, in Mathematical Foundations of Computer Science 2002, Proceedings of 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26–30, 2002. LNCS, vol. 2420 (Springer, Berlin, 2002), pp. 399–410
431.
R. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, ed. by R. Miller, J. Thatcher (Plenum, New York, 1972), pp. 45–68
444.
C. Kintala, P. Fischer, Refining nondeterminism in relativised polynomial time bounded computations. SIAM J. Comput. 9, 46–53 (1980) MathSciNetCrossRefMATH
450.
T. Kloks, C.-M. Lee, J. Liu, New algorithms for k-face cover, k-feedback vertex set, and k-disjoint cycles on plane and planar graphs, in Graph-Theoretic Concepts in Computer Science: 28th International Workshop, WG 2002, Revised Papers, Ceský Krumlov, Czech Republic, June 2002, ed. by L. Kućera. LNCS, vol. 2573 (Springer, Berlin, 2002), pp. 282–295 CrossRef
462.
A. Koutsonas, D. Thilikos, Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms. Algorithmica 60(4), 987–1003 (2011) MathSciNetCrossRefMATH
494.
D. Lokshtanov, D. Marx, S. Saurabh, Known algorithms on graphs of bounded treewidth are probably optimal, in Proceedings of the Twenty-Second Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23–25, 2011, ed. by D. Randall (SIAM, Philadelphia, 2011), pp. 777–789
495.
D. Lokshtanov, D. Marx, S. Saurabh, Lower bounds based on the exponential time hypothesis. Bull. Eur. Assoc. Theor. Comput. Sci. 84, 41–71 (2011) MathSciNet
496.
D. Lokshtanov, D. Marx, S. Saurabh, Slightly superexponential parameterized problems, in Proceedings of the Twenty-Second Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23–25, 2011, ed. by D. Randall (SIAM, Philadelphia, 2011), pp. 760–776
555.
M. Pătraşcu, R. Williams, On the possibility of faster sat algorithms, in Proceedings of the Twenty-First Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17–19, 2010, ed. by M. Charikar (SIAM, Philadelphia, 2010), pp. 1065–1075
577.
K. Regan, Finite substructure languages, in Proceedings of Fourth Annual Structure in Complexity Conference, University of Oregon, Eugene, Oregon, June 19–22, 1989 (IEEE Comput. Soc., Los Alamitos, 1989), pp. 87–96 CrossRef
591.
601.
I. Sau, D. Thilikos, Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs. J. Discrete Algorithms 8(3), 330–338 (2010) MathSciNetCrossRefMATH
615.
639.
S. Tazari, Faster approximation schemes and parameterized algorithms on H-minor-free and odd-minor-free graphs, in Mathematical Foundations of Computer Science 2010, Proceedings of 35th International Symposium, MFCS 2010, Brno, Czech Republic, August 23–27, 2010, ed. by P. Hlinený, A. Kucera (Springer, Berlin, 2010), pp. 641–652
641.
D. Thilikos, Fast sub-exponential algorithms and compactness in planar graphs, in Algorithms—ESA 2011: Proceedings of 19th Annual European Symposium, Saarbrücken, Germany, September 5–9, 2011. LNCS (Springer, Berlin, 2011), pp. 358–369 CrossRef
665.
V. William, Breaking the Coppersmith–Winograd barrier, to appear
669.
A.C.-C. Yao, Separating the polynomial-time hierarchy by oracles, in Proceedings of 26th Annual Symposium on Foundations of Computer Science, FOCS 1985, Portland, Oregon, USA, 21–23 October 1985 (IEEE Comput. Soc., Los Alamitos, 1985), pp. 1–10
Metadaten
Titel
The M-Hierarchy, and XP-Optimality
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_29