Paper Info
Title
Linear-Time Online Algorithm Inferring the Shortest Path from a Walk.
Abstract
We consider the problem of inferring an edge-labeled graph from the sequence of edge labels seen in a walk of that graph. It has been known that this problem is solvable in O(n log 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
2018
10.1007/978-3-030-00479-8_25
Lecture Notes in Computer Science
Keywords
DocType
Volume
Graph inference,Walk,Palindrome
Conference
11147
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
4
4
Name
Order
Citations
PageRank
Shintaro Narisada111.09
Diptarama Hendrian202.70
Ryo Yoshinaka317226.19
Ayumi Shinohara493688.28