Temporal flows in temporal networks

DOI10.1016/j.jcss.2019.02.003zbMath1423.68324arXiv1606.01091OpenAlexW2582496804WikidataQ62048691 ScholiaQ62048691MaRDI QIDQ2424668

Leszek Gąsieniec, Łukasz Kuszner, Eleni C. Akrida, Jurek Czyzowicz, Paul G. Spirakis

Publication date: 25 June 2019

Published in: Journal of Computer and System Sciences, Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

network flowstemporal networksrandom inputedge availability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Flows in graphs (05C21)

Related Items

Edge-Disjoint Branchings in Temporal Graphs ⋮ A theoretical and experimental study of a new algorithm for minimum cost flow in dynamic graphs ⋮ Optimizing reachability sets in temporal graphs by delaying ⋮ Simple, strict, proper, happy: a study of reachability in temporal graphs ⋮ Invited paper: Simple, strict, proper, happy: a study of reachability in temporal graphs ⋮ Approximation algorithms for the generalized incremental knapsack problem ⋮ Parameterised temporal exploration problems ⋮ Finding temporal paths under waiting time constraints ⋮ The Complexity of Finding Small Separators in Temporal Graphs ⋮ Edge-disjoint branchings in temporal digraphs ⋮ Finding Temporal Paths Under Waiting Time Constraints. ⋮ The complexity of finding small separators in temporal graphs ⋮ Temporal graph classes: a view through temporal separators ⋮ The temporal explorer who returns to the base

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Scheduling arc maintenance jobs in a network to maximize total flow over time
• Continuous and discrete flows over time
• The universally quickest transshipment problem in a certain class of dynamic networks with uniform path-lengths
• The structure and complexity of Nash equilibria for a selfish routing game
• A survey of dynamic network flows
• Multiline addressing by network flow
• An \(O(\sqrt n)\)-approximation algorithm for directed sparsest cut
• One, two, three, many, or: Complexity aspects of dynamic network flows with dedicated arcs
• Improving time bounds on maximum generalised flow computations by contracting the network
• On temporal graph exploration
• Faster Algorithms for the Generalized Network Flow Problem
• The Quickest Transshipment Problem
• On Temporally Connected Graphs of Small Cost
• Near-Optimal Distributed Maximum Flow
• Generalized Maximum Flows over Time
• Traveling Salesman Problems in Temporal Graphs
• Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees
• An Introduction to Network Flows over Time
• Flooding Time of Edge-Markovian Evolving Graphs
• Earliest Arrival Flows with Multiple Sources
• Submodular Unsplittable Flow on Trees
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• Allocating Bandwidth for Bursty Connections
• Temporal Network Optimization Subject to Connectivity Constraints
• New Approximation Schemes for Unsplittable Flow on a Path
• Towards (1 + ∊)-Approximate Flow Sparsifiers
• Quickest Flows Over Time
• Max flows in O(nm) time, or better
• Connectivity and inference problems for temporal networks

This page was built for publication: Temporal flows in temporal networks