Balanced branchings in digraphs

Jørgen Bang-Jensen; Anders Yeo

doi:10.1016/j.tcs.2015.06.026

Balanced branchings in digraphs

Jørgen Bang-Jensen, Anders Yeo

Department of Mathematics and Computer Science

University of Johannesburg

Research output: Contribution to journal › Journal article › Research › peer-review

Abstract

We study out-branchings rooted at a given vertex s with the extra requirement that these satisfy certain balance conditions, such as balancing the number of arcs out of s, the number of vertices in each subtree of the branching etc. We obtain polynomial algorithms for several of the problems and study the borderline between polynomial and NP-complete special cases of the problems.

Original language	English
Journal	Theoretical Computer Science
Volume	595
Issue number	August
Pages (from-to)	107-119
ISSN	0304-3975
DOIs	https://doi.org/10.1016/j.tcs.2015.06.026
Publication status	Published - 2015

Documents & Links

10.1016/j.tcs.2015.06.026

Cite this

@article{1abfc604745f4401be87d7a5a26b14da,

title = "Balanced branchings in digraphs",

abstract = "We study out-branchings rooted at a given vertex s with the extra requirement that these satisfy certain balance conditions, such as balancing the number of arcs out of s, the number of vertices in each subtree of the branching etc. We obtain polynomial algorithms for several of the problems and study the borderline between polynomial and NP-complete special cases of the problems.",

author = "J{\o}rgen Bang-Jensen and Anders Yeo",

year = "2015",

doi = "10.1016/j.tcs.2015.06.026",

language = "English",

volume = "595",

pages = "107--119 ",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "August",

}

TY - JOUR

T1 - Balanced branchings in digraphs

AU - Bang-Jensen, Jørgen

AU - Yeo, Anders

PY - 2015

Y1 - 2015

N2 - We study out-branchings rooted at a given vertex s with the extra requirement that these satisfy certain balance conditions, such as balancing the number of arcs out of s, the number of vertices in each subtree of the branching etc. We obtain polynomial algorithms for several of the problems and study the borderline between polynomial and NP-complete special cases of the problems.

AB - We study out-branchings rooted at a given vertex s with the extra requirement that these satisfy certain balance conditions, such as balancing the number of arcs out of s, the number of vertices in each subtree of the branching etc. We obtain polynomial algorithms for several of the problems and study the borderline between polynomial and NP-complete special cases of the problems.

U2 - 10.1016/j.tcs.2015.06.026

DO - 10.1016/j.tcs.2015.06.026

M3 - Journal article

SN - 0304-3975

VL - 595

SP - 107

EP - 119

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - August

ER -

Balanced branchings in digraphs

Abstract

Documents & Links

Fingerprint

Cite this