Balanced branchings in digraphs

J. Bang-Jensen; A. Yeo

doi:10.1016/j.tcs.2015.06.026

Balanced branchings in digraphs

J. Bang-Jensen
, A. Yeo

Mathematics and Applied Mathematics

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

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
Pages (from-to)	107-119
Number of pages	13
Journal	Theoretical Computer Science
Volume	595
DOIs	https://doi.org/10.1016/j.tcs.2015.06.026
Publication status	Published - 30 Aug 2015

Keywords

Balancing degrees
Balancing vertices
Branchings
NP-complete
Out-trees
Polynomial algorithm

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.tcs.2015.06.026

Cite this

@article{3fb325ab198c434d904381aae4fafcfb,

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.",

keywords = "Balancing degrees, Balancing vertices, Branchings, NP-complete, Out-trees, Polynomial algorithm",

author = "J. Bang-Jensen and A. Yeo",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier B.V.",

year = "2015",

month = aug,

day = "30",

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

language = "English",

volume = "595",

pages = "107--119",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Balanced branchings in digraphs

AU - Bang-Jensen, J.

AU - Yeo, A.

PY - 2015/8/30

Y1 - 2015/8/30

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.

KW - Balancing degrees

KW - Balancing vertices

KW - Branchings

KW - NP-complete

KW - Out-trees

KW - Polynomial algorithm

UR - https://www.scopus.com/pages/publications/84937393931

U2 - 10.1016/j.tcs.2015.06.026

DO - 10.1016/j.tcs.2015.06.026

M3 - Article

AN - SCOPUS:84937393931

SN - 0304-3975

VL - 595

SP - 107

EP - 119

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Balanced branchings in digraphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this