Exact and Parameterized Algorithms for Max Internal Spanning Tree

Henning Fernau 1 Serge Gaspers 2 Daniel Raible 1
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We consider the 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 O(c^n) (c ≤ 3). The main result, however, is a branching algorithm for graphs with maximum degree three. It only needs polynomial space and has a running time of O(1.8669^n) when analyzed with respect to the number of vertices. We also show that its running time is 2.1364^k n^(O(1)) when the goal is to find a spanning tree with at least k internal vertices. Both running time bounds are obtained via a Measure & Conquer analysis, the latter one being a novel use of this kind of analysis for parameterized algorithms.
Type de document :
Communication dans un congrès
WG'09: International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2009, Montpellier, France. pp.12, 2010, 〈http://www.lirmm.fr/wg2009/〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00432673
Contributeur : Serge Gaspers <>
Soumis le : lundi 16 novembre 2009 - 21:03:01
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • HAL Id : lirmm-00432673, version 1

Collections

Citation

Henning Fernau, Serge Gaspers, Daniel Raible. Exact and Parameterized Algorithms for Max Internal Spanning Tree. WG'09: International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2009, Montpellier, France. pp.12, 2010, 〈http://www.lirmm.fr/wg2009/〉. 〈lirmm-00432673〉

Partager

Métriques

Consultations de la notice

89