Daniel Binkele-Raible ; Henning Fernau - A Parameterized Measure-and-ConquerAnalysis for Finding a k-Leaf Spanning Treein an Undirected Graph

dmtcs:1256 - Discrete Mathematics & Theoretical Computer Science, March 30, 2014, Vol. 16 no. 1 - https://doi.org/10.46298/dmtcs.1256
A Parameterized Measure-and-ConquerAnalysis for Finding a k-Leaf Spanning Treein an Undirected Graph

Authors: Daniel Binkele-Raible 1; Henning Fernau 1

  • 1 Trier University

The problem of finding a spanning tree in an undirected graph with a maximum number of leaves is known to be NP-hard. We present an algorithm which finds a spanning tree with at least k leaves in time O*(3.4575k) which improves the currently best algorithm. The estimation of the running time is done by using a non-standard measure. The present paper is one of the still few examples that employ the Measure & Conquer paradigm of algorithm analysis in the area of Parameterized Algorithmics.

https://doi.org/10.46298/dmtcs.1256
Source: HAL:hal-01179218v1
Volume: Vol. 16 no. 1
Section: Discrete Algorithms
Published on: March 30, 2014
Accepted on: July 23, 2015
Submitted on: May 8, 2012
Keywords: Parameterized algorithms, graph algorithms, spanning trees,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 1502.07725
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1502.07725
  • 10.48550/arxiv.1502.07725
  • 1502.07725
The $k$-Leaf Spanning Tree Problem Admits a Klam Value of 39

Share and export

Consultation statistics

This page has been seen 341 times.
This article's PDF has been downloaded 1000 times.