The b-Branching Problem in Digraphs

Authors Naonori Kakimura, Naoyuki Kamiyama, Kenjiro Takazawa



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.12.pdf
  • Filesize: 484 kB
  • 15 pages

Document Identifiers

Author Details

Naonori Kakimura
  • Keio University, Kanagawa 223-8522, Japan
Naoyuki Kamiyama
  • Kyushu University and JST, PRESTO, Fukuoka 819-0395, Japan
Kenjiro Takazawa
  • Hosei University, Tokyo 184-8584, Japan

Cite AsGet BibTex

Naonori Kakimura, Naoyuki Kamiyama, and Kenjiro Takazawa. The b-Branching Problem in Digraphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.MFCS.2018.12

Abstract

In this paper, we introduce the concept of b-branchings in digraphs, which is a generalization of branchings serving as a counterpart of b-matchings. Here b is a positive integer vector on the vertex set of a digraph, and a b-branching is defined as a common independent set of two matroids defined by b: an arc set is a b-branching if it has at most b(v) arcs sharing the terminal vertex v, and it is an independent set of a certain sparsity matroid defined by b. We demonstrate that b-branchings yield an appropriate generalization of branchings by extending several classical results on branchings. We first present a multi-phase greedy algorithm for finding a maximum-weight b-branching. We then prove a packing theorem extending Edmonds' disjoint branchings theorem, and provide a strongly polynomial algorithm for finding optimal disjoint b-branchings. As a consequence of the packing theorem, we prove the integer decomposition property of the b-branching polytope. Finally, we deal with a further generalization in which a matroid constraint is imposed on the b(v) arcs sharing the terminal vertex v.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Greedy Algorithm
  • Packing
  • Matroid Intersection
  • Sparsity Matroid
  • Arborescence

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail