An Exact Algorithm for the Maximum Leaf Spanning Tree Problem
Identifieur interne : 001A12 ( Istex/Curation ); précédent : 001A11; suivant : 001A13An 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 :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2009.
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...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :001B29
Links to Exploration step
ISTEX:7BE882E22D197384808B21F7979B89C0EB50025FLe 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 }}
![]() | This area was generated with Dilib version V0.6.31. | ![]() |