Packing Arborescences in Acyclic Temporal Networks

神山, 直之

A temporal network is a finite directed graph in which each arc has a time label specifying the time at which its end-vertices communicate. An arborescence in a temporal network is said to be time-respecting, if the time labels on every directed path from the root in this arborescence are monotonically non-decreasing. In this paper, we consider the problem of packing time-respecting arborescences in a temporal network. Precisely speaking, we study an extension of Edmonds' arc-disjoint arborescences theorem in a temporal network. Unfortunately, it is known that a natural extension of Edmonds' arc-disjoint arborescences theorem in a temporal network does not hold. In this paper, we first show that this extension does not hold, even if an input temporal network is acyclic. Next, we prove that if an input temporal network is acyclic and pre-flow, this extension holds and we can find arc-disjoint time-respecting arborescences in polynomial time. Furthermore, we extend our main result to the problem of packing time-respecting partial arborescences.

Packing Arborescences in Acyclic Temporal Networks

この論文をさがす

説明

収録刊行物

詳細情報詳細情報について

書き出し

問題の指摘

Packing Arborescences in Acyclic Temporal Networks

この論文をさがす

説明

収録刊行物

詳細情報 詳細情報について

書き出し

問題の指摘

詳細情報詳細情報について