In search of the lost tree: Hardness and relaxation of spanning trees in temporal graphs.
Arnaud CasteigtsTimothée CorsiniPublished in: CoRR (2023)
Keyphrases
- spanning tree
- minimum spanning tree
- minimum spanning trees
- depth first search
- minimum cost
- search algorithm
- edge disjoint
- undirected graph
- search space
- minimum weight
- edge weights
- weighted graph
- root node
- spatio temporal
- temporal constraints
- temporal reasoning
- temporal information
- np hard
- minimum total cost
- graph theory
- np complete
- worst case
- computational complexity