Temporalizing digraphs via linear-size balanced bi-trees

DOI10.4230/LIPICS.STACS.2024.13MaRDI QIDQ6902712zbMATH OpenFDO

Authors Stéphane Bessy, Stéphan Thomassé, Laurent Viennot

Publication date 10 November 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2024.13

zbMATH Keywords

\#1 in-branchingbi-treedigraphforward connected pairsleft-maximal DFSout-branching in-treeout-treetemporal graphtemporalization

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Arc‐disjoint in‐ and out‐branchings in digraphs of independence number at most 2
• Decremental strongly-connected components and single-source reachability in near-linear time
• Deleting edges to restrict the size of an epidemic in temporal networks
• Digraphs
• Edge-disjoint in- and out-branchings in tournaments and related path problems
• Finding good 2-partitions of digraphs. II. Enumerable properties
• Label-connected graphs and the gossip problem
• Maximizing reachability in a temporal graph obtained by assigning starting times to a collection of walks
• Temporal network optimization subject to connectivity constraints
• Temporal Reachability Minimization: Delaying vs. Deleting
• The complexity of computing optimum labelings for temporal connectivity
• The complexity of optimal design of temporally connected graphs

This page was built for publication: Temporalizing digraphs via linear-size balanced bi-trees

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