On Temporally Connected Graphs of Small Cost

DOI10.1007/978-3-319-28684-6_8MaRDI QIDQ2788993zbMATH OpenOpenAlexFDO

Authors Eleni C. Akrida, George B. Mertzios, Leszek Gąsieniec, P. G. Spirakis

Publication date 26 February 2016

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL http://dro.dur.ac.uk/16558/1/16558.pdf

Mathematics Subject Classification ID

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

Recommendations

• On the size and the approximability of minimum temporally connected subgraphs
• The complexity of optimal design of temporally connected graphs
• On exploring always-connected temporal graphs of small pathwidth
• The complexity of finding small separators in temporal graphs
• The complexity of finding small separators in temporal graphs
• On short fastest paths in temporal graphs
• Assigning times to minimise reachability in temporal graphs
• The Complexity of Transitively Orienting Temporal Graphs
• Untangling temporal graphs of bounded degree

Cited in

(6)

• Temporal cliques admit sparse spanners
• The complexity of optimal design of temporally connected graphs
• On the size and the approximability of minimum temporally connected subgraphs
• The complexity of finding small separators in temporal graphs
• Temporal cliques admit sparse spanners
• Temporal network optimization subject to connectivity constraints

This page was built for publication: On Temporally Connected Graphs of Small Cost

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