Serveur d'exploration sur l'Université de Trèves

Attention, ce site est en cours de développement !
Attention, site généré par des moyens informatiques à partir de corpus bruts.
Les informations ne sont donc pas validées.

An Exact Algorithm for the Maximum Leaf Spanning Tree Problem

Identifieur interne : 001A12 ( Istex/Curation ); précédent : 001A11; suivant : 001A13

An Exact Algorithm for the Maximum Leaf Spanning Tree Problem

Auteurs : Henning Fernau [Allemagne] ; Joachim Kneis [Allemagne] ; Dieter Kratsch [France] ; Alexander Langer [Allemagne] ; Mathieu Liedloff [France] ; Daniel Raible [Allemagne] ; Peter Rossmanith [Allemagne]

Source :

RBID : ISTEX:7BE882E22D197384808B21F7979B89C0EB50025F

Abstract

Abstract: Given an undirected graph G with n nodes, the Maximum Leaf Spanning Tree problem asks to find a spanning tree of G with as many leaves as possible. When parameterized in the number of leaves k, this problem can be solved in time O(4 k poly(n)) using a simple branching algorithm introduced by a subset of the authors [13]. Daligault, Gutin, Kim, and Yeo [6] improved this branching algorithm and obtained a running time of O(3.72 k poly(n)). In this paper, we study the problem from an exact exponential time point of view, where it is equivalent to the Connected Dominating Set problem. For this problem Fomin, Grandoni, and Kratsch showed how to break the Ω(2 n ) barrier and proposed an O(1.9407 n ) time algorithm [10]. Based on some properties of [6] and [13], we establish a branching algorithm whose running time of O(1.8966 n ) has been analyzed using the Measure-and-Conquer technique. Finally we provide a lower bound of Ω(1.4422 n ) for the worst case running time of our algorithm.

Url:
DOI: 10.1007/978-3-642-11269-0_13

Links toward previous steps (curation, corpus...)


Links to Exploration step

ISTEX:7BE882E22D197384808B21F7979B89C0EB50025F

Le document en format XML

<record>
<TEI wicri:istexFullTextTei="biblStruct">
<teiHeader>
<fileDesc>
<titleStmt>
<title xml:lang="en">An Exact Algorithm for the Maximum Leaf Spanning Tree Problem</title>
<author>
<name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name>
<affiliation wicri:level="1">
<mods:affiliation>Universität Trier, FB 4—Abteilung Informatik, D-54286, Trier, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Universität Trier, FB 4—Abteilung Informatik, D-54286, Trier</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1">
<mods:affiliation>E-mail: fernau@uni-trier.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author>
<name sortKey="Kneis, Joachim" sort="Kneis, Joachim" uniqKey="Kneis J" first="Joachim" last="Kneis">Joachim Kneis</name>
<affiliation wicri:level="1">
<mods:affiliation>Department of Computer Science, RWTH Aachen University, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Department of Computer Science, RWTH Aachen University</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1">
<mods:affiliation>E-mail: kneis@cs.rwth-aachen.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author>
<name sortKey="Kratsch, Dieter" sort="Kratsch, Dieter" uniqKey="Kratsch D" first="Dieter" last="Kratsch">Dieter Kratsch</name>
<affiliation wicri:level="1">
<mods:affiliation>Laboratoire d’Informatique Théorique et Appliquée, Université Paul Verlaine - Metz, 57045, Metz Cedex 01, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>Laboratoire d’Informatique Théorique et Appliquée, Université Paul Verlaine - Metz, 57045, Metz Cedex 01</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1">
<mods:affiliation>E-mail: kratsch@univ-metz.fr</mods:affiliation>
<country wicri:rule="url">France</country>
</affiliation>
</author>
<author>
<name sortKey="Langer, Alexander" sort="Langer, Alexander" uniqKey="Langer A" first="Alexander" last="Langer">Alexander Langer</name>
<affiliation wicri:level="1">
<mods:affiliation>Department of Computer Science, RWTH Aachen University, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Department of Computer Science, RWTH Aachen University</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1">
<mods:affiliation>E-mail: langer@cs.rwth-aachen.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author>
<name sortKey="Liedloff, Mathieu" sort="Liedloff, Mathieu" uniqKey="Liedloff M" first="Mathieu" last="Liedloff">Mathieu Liedloff</name>
<affiliation wicri:level="1">
<mods:affiliation>Laboratoire d’Informatique Fondamentale d’Orléans, Université d’Orléans, 45067, Orléans Cedex 2, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>Laboratoire d’Informatique Fondamentale d’Orléans, Université d’Orléans, 45067, Orléans Cedex 2</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1">
<mods:affiliation>E-mail: liedloff@univ-orleans.fr</mods:affiliation>
<country wicri:rule="url">France</country>
</affiliation>
</author>
<author>
<name sortKey="Raible, Daniel" sort="Raible, Daniel" uniqKey="Raible D" first="Daniel" last="Raible">Daniel Raible</name>
<affiliation wicri:level="1">
<mods:affiliation>Universität Trier, FB 4—Abteilung Informatik, D-54286, Trier, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Universität Trier, FB 4—Abteilung Informatik, D-54286, Trier</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1">
<mods:affiliation>E-mail: raible@uni-trier.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author>
<name sortKey="Rossmanith, Peter" sort="Rossmanith, Peter" uniqKey="Rossmanith P" first="Peter" last="Rossmanith">Peter Rossmanith</name>
<affiliation wicri:level="1">
<mods:affiliation>Department of Computer Science, RWTH Aachen University, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Department of Computer Science, RWTH Aachen University</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1">
<mods:affiliation>E-mail: rossmani@cs.rwth-aachen.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt>
<idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:7BE882E22D197384808B21F7979B89C0EB50025F</idno>
<date when="2009" year="2009">2009</date>
<idno type="doi">10.1007/978-3-642-11269-0_13</idno>
<idno type="url">https://api.istex.fr/document/7BE882E22D197384808B21F7979B89C0EB50025F/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001B29</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001B29</idno>
<idno type="wicri:Area/Istex/Curation">001A12</idno>
</publicationStmt>
<sourceDesc>
<biblStruct>
<analytic>
<title level="a" type="main" xml:lang="en">An Exact Algorithm for the Maximum Leaf Spanning Tree Problem</title>
<author>
<name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name>
<affiliation wicri:level="1">
<mods:affiliation>Universität Trier, FB 4—Abteilung Informatik, D-54286, Trier, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Universität Trier, FB 4—Abteilung Informatik, D-54286, Trier</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1">
<mods:affiliation>E-mail: fernau@uni-trier.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author>
<name sortKey="Kneis, Joachim" sort="Kneis, Joachim" uniqKey="Kneis J" first="Joachim" last="Kneis">Joachim Kneis</name>
<affiliation wicri:level="1">
<mods:affiliation>Department of Computer Science, RWTH Aachen University, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Department of Computer Science, RWTH Aachen University</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1">
<mods:affiliation>E-mail: kneis@cs.rwth-aachen.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author>
<name sortKey="Kratsch, Dieter" sort="Kratsch, Dieter" uniqKey="Kratsch D" first="Dieter" last="Kratsch">Dieter Kratsch</name>
<affiliation wicri:level="1">
<mods:affiliation>Laboratoire d’Informatique Théorique et Appliquée, Université Paul Verlaine - Metz, 57045, Metz Cedex 01, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>Laboratoire d’Informatique Théorique et Appliquée, Université Paul Verlaine - Metz, 57045, Metz Cedex 01</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1">
<mods:affiliation>E-mail: kratsch@univ-metz.fr</mods:affiliation>
<country wicri:rule="url">France</country>
</affiliation>
</author>
<author>
<name sortKey="Langer, Alexander" sort="Langer, Alexander" uniqKey="Langer A" first="Alexander" last="Langer">Alexander Langer</name>
<affiliation wicri:level="1">
<mods:affiliation>Department of Computer Science, RWTH Aachen University, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Department of Computer Science, RWTH Aachen University</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1">
<mods:affiliation>E-mail: langer@cs.rwth-aachen.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author>
<name sortKey="Liedloff, Mathieu" sort="Liedloff, Mathieu" uniqKey="Liedloff M" first="Mathieu" last="Liedloff">Mathieu Liedloff</name>
<affiliation wicri:level="1">
<mods:affiliation>Laboratoire d’Informatique Fondamentale d’Orléans, Université d’Orléans, 45067, Orléans Cedex 2, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>Laboratoire d’Informatique Fondamentale d’Orléans, Université d’Orléans, 45067, Orléans Cedex 2</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1">
<mods:affiliation>E-mail: liedloff@univ-orleans.fr</mods:affiliation>
<country wicri:rule="url">France</country>
</affiliation>
</author>
<author>
<name sortKey="Raible, Daniel" sort="Raible, Daniel" uniqKey="Raible D" first="Daniel" last="Raible">Daniel Raible</name>
<affiliation wicri:level="1">
<mods:affiliation>Universität Trier, FB 4—Abteilung Informatik, D-54286, Trier, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Universität Trier, FB 4—Abteilung Informatik, D-54286, Trier</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1">
<mods:affiliation>E-mail: raible@uni-trier.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author>
<name sortKey="Rossmanith, Peter" sort="Rossmanith, Peter" uniqKey="Rossmanith P" first="Peter" last="Rossmanith">Peter Rossmanith</name>
<affiliation wicri:level="1">
<mods:affiliation>Department of Computer Science, RWTH Aachen University, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Department of Computer Science, RWTH Aachen University</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1">
<mods:affiliation>E-mail: rossmani@cs.rwth-aachen.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series>
<title level="s">Lecture Notes in Computer Science</title>
<imprint>
<date>2009</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
<idno type="istex">7BE882E22D197384808B21F7979B89C0EB50025F</idno>
<idno type="DOI">10.1007/978-3-642-11269-0_13</idno>
<idno type="ChapterID">13</idno>
<idno type="ChapterID">Chap13</idno>
</biblStruct>
</sourceDesc>
<seriesStmt>
<idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc>
<textClass></textClass>
<langUsage>
<language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front>
<div type="abstract" xml:lang="en">Abstract: Given an undirected graph G with n nodes, the Maximum Leaf Spanning Tree problem asks to find a spanning tree of G with as many leaves as possible. When parameterized in the number of leaves k, this problem can be solved in time O(4 k poly(n)) using a simple branching algorithm introduced by a subset of the authors [13]. Daligault, Gutin, Kim, and Yeo [6] improved this branching algorithm and obtained a running time of O(3.72 k poly(n)). In this paper, we study the problem from an exact exponential time point of view, where it is equivalent to the Connected Dominating Set problem. For this problem Fomin, Grandoni, and Kratsch showed how to break the Ω(2 n ) barrier and proposed an O(1.9407 n ) time algorithm [10]. Based on some properties of [6] and [13], we establish a branching algorithm whose running time of O(1.8966 n ) has been analyzed using the Measure-and-Conquer technique. Finally we provide a lower bound of Ω(1.4422 n ) for the worst case running time of our algorithm.</div>
</front>
</TEI>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001A12 | SxmlIndent | more

Ou

HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 001A12 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Rhénanie
   |area=    UnivTrevesV1
   |flux=    Istex
   |étape=   Curation
   |type=    RBID
   |clé=     ISTEX:7BE882E22D197384808B21F7979B89C0EB50025F
   |texte=   An Exact Algorithm for the Maximum Leaf Spanning Tree Problem
}}

Wicri

This area was generated with Dilib version V0.6.31.
Data generation: Sat Jul 22 16:29:01 2017. Site generation: Wed Feb 28 14:55:37 2024