Exact and Parameterized Algorithms for Max Internal Spanning Tree
| Autor: | Henning Fernau, Daniel Binkele-Raible, Mathieu Liedloff, Serge Gaspers |
|---|---|
| Přispěvatelé: | Universität Trier, Institute of Information Systems, Vienna University of Technology (TU Wien), Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), Ecole Nationale Supérieure d'Ingénieurs de Bourges-Université d'Orléans (UO) |
| Rok vydání: | 2011 |
| Předmět: |
Discrete mathematics
021103 operations research Spanning tree General Computer Science Degree (graph theory) Generalization Applied Mathematics [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology 01 natural sciences Measure (mathematics) Computer Science Applications Combinatorics 010201 computation theory & mathematics Bounded function Theory of computation ComputingMilieux_MISCELLANEOUS Hamiltonian path problem PSPACE Mathematics |
| Zdroj: | Algorithmica Algorithmica, Springer Verlag, 2013, 65 (1), pp.95-128. ⟨10.1007/s00453-011-9575-5⟩ |
| ISSN: | 1432-0541 0178-4617 |
| Popis: | We consider the $\mathcal{NP}$-hard problem of finding a spanning tree with a maximum number of internal vertices. This problem is a generalization of the famous Hamiltonian Path problem. Our dynamic-programming algorithms for general and degree-bounded graphs have running times of the form $\mathcal{O}^{*}(c^{n})$ with c≤2. For graphs with bounded degree, c |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink