### 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 2^{O(k log2k)}·n^{O(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 language | English (US) |
---|---|

Title of host publication | FSTTCS 2007 |

Subtitle of host publication | Foundations of Software Technology and Theoretical Computer Science - 27th International Conference, Proceedings |

Publisher | Springer Verlag |

Pages | 316-327 |

Number of pages | 12 |

ISBN (Print) | 9783540770497 |

DOIs | |

State | Published - Jan 1 2007 |

Externally published | Yes |

Event | 27th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2007 - New Delhi, India Duration: Dec 12 2007 → Dec 14 2007 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 4855 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 27th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2007 |
---|---|

Country | India |

City | New Delhi |

Period | 12/12/07 → 12/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

*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