On the Size and the Approximability of Minimum Temporally Connected Subgraphs

DOI10.4230/LIPIcs.ICALP.2016.149zbMath1388.68299arXiv1602.06411OpenAlexW2962819912MaRDI QIDQ4598293

Dimitris Fotakis, Kyriakos Axiotis

Publication date: 19 December 2017

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

zbMATH Keywords

approximation algorithmstemporal graphstemporal connectivity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (18)

As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ Blackout-tolerant temporal spanners ⋮ Simple, strict, proper, happy: a study of reachability in temporal graphs ⋮ Blackout-tolerant temporal spanners ⋮ Sharp Thresholds in Random Simple Temporal Graphs ⋮ Invited paper: Simple, strict, proper, happy: a study of reachability in temporal graphs ⋮ Computing maximum matchings in temporal graphs ⋮ Finding temporal paths under waiting time constraints ⋮ The Complexity of Finding Small Separators in Temporal Graphs ⋮ Coloring temporal graphs ⋮ Finding Temporal Paths Under Waiting Time Constraints. ⋮ The complexity of finding small separators in temporal graphs ⋮ Temporal graph classes: a view through temporal separators ⋮ Temporal cliques admit sparse spanners ⋮ Feedback edge sets in temporal graphs ⋮ Edge exploration of temporal graphs ⋮ Edge exploration of temporal graphs ⋮ Temporal Cliques Admit Sparse Spanners

This page was built for publication: On the Size and the Approximability of Minimum Temporally Connected Subgraphs