An FPT algorithm for temporal graph untangling

DOI10.4230/LIPICS.IPEC.2023.12MaRDI QIDQ6926198zbMATH OpenFDO

Authors Riccardo Dondi, Manuel Lafond

Publication date 24 September 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2023.12

zbMATH Keywords

graph algorithmsparameterized complexityvertex covertemporal graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Cites work

• Almost 2-SAT is fixed-parameter tractable
• Connectivity and inference problems for temporal networks
• Directed flow-augmentation
• Edge exploration of temporal graphs
• Finding colorful paths in temporal graphs
• Flow-augmentation. III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
• Königsberg sightseeing: Eulerian walks in temporal graphs
• On temporal graph exploration
• Representative sets and irrelevant vertices: new tools for kernelization
• Temporal graph classes: a view through temporal separators
• 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
• Timeline cover in temporal graphs: exact and approximation algorithms
• Untangling temporal graphs of bounded degree

Cited in

(1)

• An FPT algorithm for timeline cover

This page was built for publication: An FPT algorithm for temporal graph untangling

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