Edge-disjoint branchings in temporal digraphs

DOI10.37236/10229MaRDI QIDQ2236804zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 26 October 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2002.12694

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

spanning branchingbase static digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: A temporal digraph $calG$ is a triple $(G,gamma,lambda)$ where $G$ is a digraph, $gamma$ is a function on $V(G)$ that tells us the timestamps when a vertex is active, and $lambda$ is a function on $E(G)$ that tells for each $uvinE(G)$ when $u$ and $v$ are linked. Given a static digraph $G$, and a subset $RsubseteqV(G)$, a spanning branching with root $R$ is a subdigraph of $G$ that has exactly one path from $R$ to each $vinV(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 at given $R_1,cdots,R_k$. We introduce and investigate different definitions of spanning branchings, and of edge-disjointness in the context of temporal graphs. A branching $calB$ 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 $v$ can be reached from the root at every time where $v$ is active. On the other hand, two branchings ${calB}_1$ and ${calB}_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 $mathsfNP$-complete, even under very strict assumptions.

Recommendations

• On packing arborescences in temporal networks
• Edge exploration of temporal graphs
• Feedback edge sets in temporal graphs
• Connectivity and inference problems for temporal networks
• The \(b\)-branching problem in digraphs

Cites work

• scientific article; zbMATH DE number 3659627 (Why is no real title available?)
• scientific article; zbMATH DE number 3488914 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• scientific article; zbMATH DE number 961960 (Why is no real title available?)
• A good algorithm for edge-disjoint branching
• An introduction to temporal graphs: an algorithmic perspective
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Connectivity and inference problems for temporal networks
• Edge-Disjoint Branchings in Temporal Graphs
• Edge-disjoint branching in directed multigraphs
• Integral decomposition in polyhedra
• On edge-disjoint branchings
• On two minimax theorems in graph
• Parameterized algorithms
• Parameterized tractability of edge-disjoint paths on directed acyclic graphs
• Temporal network optimization subject to connectivity constraints
• The complexity of satisfiability problems
• The directed subgraph homeomorphism problem
• The nature of computation

Cited in

(5)

• scientific article; zbMATH DE number 7559396 (Why is no real title available?)
• On finding separators in temporal split and permutation graphs
• Mengerian graphs: characterization and recognition
• On computing optimal temporal branchings and spanning subgraphs
• Edge-Disjoint Branchings in Temporal Graphs

This page was built for publication: Edge-disjoint branchings in temporal digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2236804)