Edge-disjoint branchings in temporal digraphs
type: Item
instance of: scholarly article
title: Edge-disjoint branchings in temporal digraphs
zbMATH Open document ID: 1476.05065
DOI: 10.37236/10229
author: Yanyan Li
published in: The Electronic Journal of Combinatorics
publication date: 2021-10-26T00:00:00Z
full work available at URL: https://arxiv.org/abs/2002.12694
review text: Summary: A temporal digraph \(\mathcal{G}\) is a triple \((G, \gamma, \lambda)\) where \(G\) is a digraph, \(\gamma\) is a function on \(V(G)\) that tells us the time stamps when a vertex is active, and \(\lambda\) is a function on \(E(G)\) that tells for each \(uv\in E(G)\) when \(u\) and \(v\) are linked. Given a static digraph \(G\), and a subset \(R\subseteq V(G)\), a spanning branching with root \(R\) is a subdigraph of \(G\) that has exactly one path from \(R\) to each \(v\in V(G)\). In this paper, we consider the temporal version of Edmonds' classical result about the problem of finding \(k\) edge-disjoint spanning branchings respectively rooted in given \(R_1,\dots,R_k\). We introduce and investigate different definitions of spanning branchings, and of edge-disjointness in the context of temporal digraphs. A branching \(\mathcal{B}\) is vertex-spanning if the root is able to reach each vertex \(v\) of \(G\) at some time where \(v\) is active, while it is temporal-spanning if each \(v\) can be reached from the root at every time where \(v\) is active. On the other hand, two branchings \(\mathcal{B}_1\) and \(\mathcal{B}_2\) are edge-disjoint if they do not use the same edge of \(G\), and are temporal-edge-disjoint if they can use the same edge of \(G\) but at different times. This lead us to four definitions of disjoint spanning branchings and we prove that, unlike the static case, only one of these can be computed in polynomial time, namely the temporal-edge-disjoint temporal-spanning branchings problem, while the other versions are NP-complete, even under very strict assumptions.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7414022
zbMATH Keywords: spanning branching
zbMATH Keywords: base static digraph
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W3206407623
arXiv ID: 2002.12694
cites work: Temporal flows in temporal networks
cites work: Q5689807
cites work: COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
cites work: Edge-Disjoint Branchings in Temporal Graphs
cites work: Parameterized Algorithms
cites work: Q4070624
cites work: The directed subgraph homeomorphism problem
cites work: Q3858297
cites work: On edge-disjoint branchings
cites work: Connectivity and inference problems for temporal networks
cites work: On two minimax theorems in graph
cites work: Integral decomposition in polyhedra
cites work: Temporal network optimization subject to connectivity constraints
cites work: An Introduction to Temporal Graphs: An Algorithmic Perspective*
cites work: Q3090774
cites work: The complexity of satisfiability problems
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: Edge-disjoint branching in directed multigraphs
cites work: Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs
cites work: A good algorithm for edge-disjoint branching
cites work: Q4869540
description: scientific article