Branching in digraphs with many and few leaves: Structural and algorithmic results

Jørgen Bang-Jensen, Gregory Gutin*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingBook chapterResearchpeer-review

Abstract

A subgraph T of a digraph D is called an out-tree if T is an oriented tree with just one vertex s of in-degree zero. A spanning out-tree is called an out-branching. A vertex x of an out-branching B is called a leaf if the out-degree of x is zero. This is a survey on out-branchings with minimum and maximum number of leaves covering both structural and algorithmic results.

Original languageEnglish
Title of host publicationOptimization Problems in Graph Theory : In Honor of Gregory Z. Gutin's 60th Birthday
EditorsBoris Goldengorin
PublisherSpringer
Publication dateSep 2018
Pages93-106
ISBN (Print)978-3-319-94829-4
ISBN (Electronic)978-3-319-94830-0
DOIs
Publication statusPublished - Sep 2018
SeriesSpringer Optimization and Its Applications
Volume139
ISSN1931-6828

Fingerprint

Dive into the research topics of 'Branching in digraphs with many and few leaves: Structural and algorithmic results'. Together they form a unique fingerprint.

Cite this