Edge-disjoint branchings in temporal digraphs

DOI10.37236/10229zbMATH Open1476.05065arXiv2002.12694OpenAlexW3206407623MaRDI QIDQ2236804FDOQ2236804

Authors: Yanyan Li 

Publication date: 26 October 2021

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

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.

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

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

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

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)

Cites Work

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

Cited In (5)

• Title not available (Why is that?)
• 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)