Untangling temporal graphs of bounded degree

DOI10.1016/J.TCS.2023.114040MaRDI QIDQ6165555zbMATH OpenOpenAlexFDO

Authors Riccardo Dondi

Publication date 1 August 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.tcs.2023.114040

zbMATH Keywords

computational complexitygraph algorithmstemporal graphsvertex cover

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• An introduction to temporal graphs: an algorithmic perspective
• Connectivity and inference problems for temporal networks
• Edge exploration of temporal graphs
• Finding colorful paths in temporal graphs
• Königsberg sightseeing: Eulerian walks in temporal graphs
• Reducibility among combinatorial problems
• Sliding window temporal graph coloring
• Some APX-completeness results for cubic graphs
• Temporal vertex cover with a sliding time window
• The complexity of finding small separators in temporal graphs
• The network-untangling problem: from interactions to activity timelines
• The temporal explorer who returns to the base

Cited in

(9)

• On Temporally Connected Graphs of Small Cost
• Symbolically Bounding the Drift in Time-Constrained MSC Graphs
• ON THE HARDNESS OF RECOGNIZING BUNDLES IN TIME TABLE GRAPHS
• Preface
• An FPT algorithm for temporal graph untangling
• An FPT algorithm for timeline cover
• Exact and approximation algorithms for covering timeline in temporal graphs
• Partial temporal vertex cover with bounded activity intervals
• Temporal dominating set and temporal vertex cover under the lens of degree restrictions

This page was built for publication: Untangling temporal graphs of bounded degree

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