Paper Info
Title
Linear-Time Online Algorithm for Inferring the Shortest Path Graph from a Walk Label
Abstract
We consider the problem of inferring an edge-labeled graph from the sequence of edge labels seen in a walk on that graph. It has been known that this problem is solvable in O(nlog⁡n) time when the targets are path or cycle graphs. This paper presents an online algorithm for the problem of this restricted case that runs in O(n) time, based on Manacher's algorithm for computing all the maximal palindromes in a string.
Year
DOI
Venue
2020
10.1016/j.tcs.2019.10.029
Theoretical Computer Science
Keywords
Field
DocType
Graph inference,String rewriting,Palindrome
Discrete mathematics,Graph,Online algorithm,Combinatorics,Shortest path problem,Palindrome,Time complexity,Mathematics
Journal
Volume
ISSN
Citations 
812
0304-3975
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Shintaro Narisada100.34
Diptarama Hendrian202.70
Ryo Yoshinaka317226.19
Ayumi Shinohara493688.28