Arc‐Disjoint In‐ and Out‐Branchings With the Same Root in Locally Semicomplete Digraphs | Zendy

BangJensen Jørgen | Zendy; Huang Jing | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Arc‐Disjoint In‐ and Out‐Branchings With the Same Root in Locally Semicomplete Digraphs

Author(s) -

BangJensen Jørgen,

Huang Jing

Publication year - 2014

Publication title -

journal of graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 54

eISSN - 1097-0118

pISSN - 0364-9024

DOI - 10.1002/jgt.21786

Subject(s) - digraph , mathematics , combinatorics , disjoint sets , vertex (graph theory) , constructive , mathematical proof , arc (geometry) , transitive relation , discrete mathematics , graph , computer science , geometry , process (computing) , operating system

Deciding whether a digraph contains a pair of arc‐disjoint in‐ and out‐branchings rooted at a specified vertex is a well‐known NP‐complete problem (as proved by Thomassen, see [2][J. Bang‐Jensen, 1991]). This problem has been shown to be polynomial time solvable for semicomplete digraphs [2][J. Bang‐Jensen, 1991] and for quasi‐transitive digraphs [6][J. Bang‐Jensen, 1995]. In this article, we study the problem for locally semicomplete digraphs. We characterize locally semicomplete digraphs that contain a pair of arc‐disjoint in‐ and out‐branchings rooted at a specified vertex. Our proofs are constructive and imply the existence of a polynomial time algorithm for finding the desired branchings when they exist. Our results generalizes those from [2][J. Bang‐Jensen, 1991] for semicomplete digraphs and solves an open problem from [4][J. Bang‐Jensen, 1998].

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research