Branching in Digraphs with Many and Few Leaves: Structural and Algorithmic Results

Jørgen Bang-Jensen () and Gregory Gutin ()
Additional contact information
Jørgen Bang-Jensen: IMADA, University of Southern Denmark
Gregory Gutin: University of London

A chapter in Optimization Problems in Graph Theory, 2018, pp 93-106 from Springer

Abstract: 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.

Keywords: Algorithmic Results; Acyclic Digraph; General Digraphs; Input Digraph; fixed-parameter Tractable (FPT) (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-319-94830-0_5

Ordering information: This item can be ordered from
http://www.springer.com/9783319948300

DOI: 10.1007/978-3-319-94830-0_5

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().