A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems (Englisch)
- Neue Suche nach: Fellows, M.R.
- Neue Suche nach: Guo, J.
- Neue Suche nach: Moser, H.
- Neue Suche nach: Niedermeier, R.
- Neue Suche nach: Fellows, M.R.
- Neue Suche nach: Guo, J.
- Neue Suche nach: Moser, H.
- Neue Suche nach: Niedermeier, R.
- Neue Suche nach: Kralovic, Rastislav
- Neue Suche nach: Niwinski, Damian
In:
Symposium on Mathematical Foundations of Computer Science MFCS 2009
5734
;
319-330
;
2009
-
ISBN:
-
ISSN:
- Aufsatz (Konferenz) / Print
-
Titel:A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
-
Beteiligte:Fellows, M.R. ( Autor:in ) / Guo, J. ( Autor:in ) / Moser, H. ( Autor:in ) / Niedermeier, R. ( Autor:in ) / Kralovic, Rastislav / Niwinski, Damian
-
Kongress:34th, Symposium on Mathematical Foundations of Computer Science MFCS 2009 ; 2009 ; High Tatras, Slovakia
-
Erschienen in:Symposium on Mathematical Foundations of Computer Science MFCS 2009 , 5734 ; 319-330LECTURE NOTES IN COMPUTER SCIENCE , 5734 ; 319-330
-
Verlag:
- Neue Suche nach: Springer
-
Erscheinungsort:Berlin
-
Erscheinungsdatum:01.01.2009
-
Format / Umfang:12 pages
-
Anmerkungen:Includes bibliographical references and author index. Also issued online.
-
ISBN:
-
ISSN:
-
Medientyp:Aufsatz (Konferenz)
-
Format:Print
-
Sprache:Englisch
-
Schlagwörter:
-
Datenquelle:
© Metadata Copyright the British Library Board and other contributors. All rights reserved.
Inhaltsverzeichnis Konferenzband
Die Inhaltsverzeichnisse werden automatisch erzeugt und basieren auf den im Index des TIB-Portals verfügbaren Einzelnachweisen der enthaltenen Beiträge. Die Anzeige der Inhaltsverzeichnisse kann daher unvollständig oder lückenhaft sein.
- 1
-
Four Subareas of the Theory of Constraints, and Their LinksAtserias, A. et al. | 2009
- 2
-
Synchronization of Regular AutomataCaucal, D. et al. | 2009
- 24
-
Stochastic Process CreationEsparza, J. et al. | 2009
- 34
-
Stochastic Games with Finitary ObjectivesChatterjee, K. / Henzinger, T.A. / Horn, F. et al. | 2009
- 55
-
Stochastic Data StreamsMuthukrishnan, S. et al. | 2009
- 56
-
Recent Advances in Population ProtocolsChatzigiannakis, I. / Michail, O. / Spirakis, P.G. et al. | 2009
- 77
-
How to Sort a TrainWidmayer, P. et al. | 2009
- 78
-
Arithmetic Circuits, Monomial Algebras and Finite AutomataArvind, V. / Joglekar, P.S. et al. | 2009
- 90
-
An Improved Approximation Bound for Spanning Star Forest and Color SavingAthanassopoulos, S. / Caragiannis, I. / Kaklamanis, C. / Kyropoulou, M. et al. | 2009
- 102
-
Energy-Efficient Communication in Multi-interface Wireless NetworksAthanassopoulos, S. / Caragiannis, I. / Kaklamanis, C. / Papaioannou, E. et al. | 2009
- 112
-
Private Capacities in Mechanism DesignAuletta, V. / Penna, P. / Persiano, G. et al. | 2009
- 124
-
Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring RulesBetzler, N. / Dorn, B. et al. | 2009
- 137
-
Sampling Edge Covers in 3-Regular GraphsBezakova, I. / Rummler, W.A. et al. | 2009
- 149
-
Balanced Paths in Colored GraphsBianco, A. / Faella, M. / Mogavero, F. / Murano, A. et al. | 2009
- 162
-
Few Product Gates But Many ZerosBorchert, B. / McKenzie, P. / Reinhardt, K. et al. | 2009
- 175
-
Branching Programs for Tree EvaluationBraverman, M. / Cook, S. / McKenzie, P. / Santhanam, R. / Wehr, D. et al. | 2009
- 187
-
A Dichotomy Theorem for Polynomial EvaluationBriquel, I. / Koiran, P. et al. | 2009
- 199
-
DP-Complete Problems Derived from Extremal NP-Complete PropertiesCao, Y. / Culberson, J. / Stewart, L. et al. | 2009
- 211
-
The Synchronization Problem for Locally Strongly Transitive AutomataCarpi, A. / D Alessandro, F. et al. | 2009
- 223
-
Constructing BramblesChapelle, M. / Mazoit, F. / Todinca, I. et al. | 2009
- 235
-
Self-indexed Text Compression Using Straight-Line ProgramsClaude, F. / Navarro, G. et al. | 2009
- 247
-
Security and Tradeoffs of the Akl-Taylor Scheme and Its VariantsD Arco, P. / De Santis, A. / Ferrara, A.L. / Masucci, B. et al. | 2009
- 258
-
Parameterized Complexity Classes under Logical ReductionsDawar, A. / He, Y. et al. | 2009
- 270
-
The Communication Complexity of Non-signaling DistributionsDegorre, J. / Kaplan, M. / Laplante, S. / Roland, J. et al. | 2009
- 282
-
How to Use Spanning Trees to Navigate in Graphs (Extended Abstract)Dragan, F.F. / Xiang, Y. et al. | 2009
- 295
-
Representing Groups on GraphsDutta, S. / Kurur, P.P. et al. | 2009
- 307
-
Admissible Strategies in Infinite Games over GraphsFaella, M. et al. | 2009
- 319
-
A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion ProblemsFellows, M.R. / Guo, J. / Moser, H. / Niedermeier, R. et al. | 2009
- 331
-
Future-Looking Logics on Data Words and TreesFigueira, D. / Segoufin, L. et al. | 2009
- 344
-
A By-Level Analysis of Multiplicative Exponential Linear LogicGaboardi, M. / Roversi, L. / Vercelli, L. et al. | 2009
- 356
-
Hyper-minimisation Made EfficientGawrychowski, P. / Jez, A. et al. | 2009
- 369
-
Regular Expressions with Counting: Weak versus Strong DeterminismGelade, W. / Gyssens, M. / Martens, W. et al. | 2009
- 382
-
Choosability of P~5-Free GraphsGolovach, P.A. / Heggernes, P. et al. | 2009
- 392
-
Time-Bounded Kolmogorov Complexity and Solovay FunctionsHolzl, R. / Kraling, T. / Merkle, W. et al. | 2009
- 403
-
The Longest Path Problem Is Polynomial on Interval GraphsIoannidou, K. / Mertzios, G.B. / Nikolopoulos, S.D. et al. | 2009
- 415
-
Synthesis for Structure Rewriting SystemsKaiser, L. et al. | 2009
- 427
-
On the Hybrid Extension of CTL and CTL^+Kara, A. / Weber, V. / Lange, M. / Schwentick, T. et al. | 2009
- 439
-
Bounds on Non-surjective Cellular AutomataKari, J. / Vanier, P. / Zeume, T. et al. | 2009
- 451
-
FO Model Checking on Nested Pushdown TreesKartzow, A. et al. | 2009
- 464
-
The Prismoid of ResourcesKesner, D. / Renaud, F. et al. | 2009
- 477
-
A Dynamic Algorithm for Reachability Games Played on TreesKhoussainov, B. / Liu, J. / Khaliq, I. et al. | 2009
- 489
-
An Algebraic Characterization of Semirings for Which the Support of Every Recognizable Series Is RecognizableKirsten, D. et al. | 2009
- 501
-
Graph Decomposition for Improving Memoryless Periodic ExplorationKosowski, A. / Navarra, A. et al. | 2009
- 513
-
On FO^2 Quantifier Alternation over WordsKufleitner, M. / Weil, P. et al. | 2009
- 525
-
On the Recognizability of Self-generating SetsKarki, T. / Lacroix, A. / Rigo, M. et al. | 2009
- 537
-
The Isomorphism Problem for k-Trees Is Complete for LogspaceKobler, J. / Kuhnert, S. et al. | 2009
- 549
-
Snake-Deterministic Tiling SystemsLonati, V. / Pradella, M. et al. | 2009
- 561
-
Query Automata for Nested WordsMadhusudan, P. / Viswanathan, M. et al. | 2009
- 574
-
A General Class of Models of H^*Manzonetto, G. et al. | 2009
- 587
-
The Complexity of Satisfiability for Fragments of Hybrid Logic-Part IMeier, A. / Mundhenk, M. / Schneider, T. / Thomas, M. / Weber, V. / Weiss, F. et al. | 2009
- 600
-
Colouring Non-sparse Random Intersection GraphsNikoletseas, S. / Raptopoulos, C. / Spirakis, P.G. et al. | 2009
- 612
-
On the Structure of Optimal Greedy Computation (for Job Scheduling)Papakonstantinou, P.A. et al. | 2009
- 624
-
A Probabilistic PTAS for Shortest Common SuperstringPlociennik, K. et al. | 2009
- 636
-
The Cost of Stability in Network Flow GamesResnick, E. / Bachrach, Y. / Meir, R. / Rosenschein, J.S. et al. | 2009
- 651
-
(Un)Decidability of Injectivity and Surjectivity in One-Dimensional Sand AutomataRichard, G. et al. | 2009
- 663
-
Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers NormRotteler, M. et al. | 2009
- 675
-
From Parity and Payoff Games to Linear ProgrammingSchewe, S. et al. | 2009
- 687
-
Partial Randomness and Dimension of Recursively Enumerable RealsTadaki, K. et al. | 2009
- 700
-
Partial Solution and EntropyTakaoka, T. et al. | 2009
- 712
-
On Pebble Automata for Data Languages with Decidable Emptiness ProblemTan, T. et al. | 2009
- 724
-
Size and Energy of Threshold Circuits Computing Mod FunctionsUchizawa, K. / Nishizeki, T. / Takimoto, E. et al. | 2009
- 736
-
Points on Computable Curves of Computable LengthsRettinger, R. / Zheng, X. et al. | 2009
- 744
-
The Expressive Power of Binary Submodular FunctionsZivny, S. / Cohen, D.A. / Jeavons, P.G. et al. | 2009