Better algorithms and bounds for directed maximum leaf problems

Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, Saket Saurabh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations

Abstract

The DIRECTED MAXIMUM LEAF OUT-BRANCHING problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we improve known parameterized algorithms and combinatorial bounds on the number of leaves in out-branchings. We show that - every strongly connected digraph D of order n with minimum indegree at least 3 has an out-branching with at least (n/4)1/3 - 1 leaves; - if a strongly connected digraph D does not contain an out-branching with k leaves, then the pathwidth of its underlying graph is O(k log k); - it can be decided in time 2O(k log2k)·nO(1) whether a strongly connected digraph on n vertices has an out-branching with at least k leaves. All improvements use properties of extremal structures obtained after applying local search and properties of some out-branching decompositions.

Original languageEnglish (US)
Title of host publicationFSTTCS 2007
Subtitle of host publicationFoundations of Software Technology and Theoretical Computer Science - 27th International Conference, Proceedings
PublisherSpringer Verlag
Pages316-327
Number of pages12
ISBN (Print)9783540770497
DOIs
StatePublished - Jan 1 2007
Externally publishedYes
Event27th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2007 - New Delhi, India
Duration: Dec 12 2007Dec 14 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4855 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other27th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2007
CountryIndia
CityNew Delhi
Period12/12/0712/14/07

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Better algorithms and bounds for directed maximum leaf problems'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Fomin, F. V., Gutin, G., Krivelevich, M., & Saurabh, S. (2007). Better algorithms and bounds for directed maximum leaf problems. In FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science - 27th International Conference, Proceedings (pp. 316-327). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4855 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-77050-3_26