@inproceedings{418b030812c64a7c9dfea93b91b56c9c,
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{\textquoteright}s algorithm for computing all the maximal palindromes in a string.",
keywords = "Graph inference, Palindrome, Walk",
author = "Shintaro Narisada and Diptarama Hendrian and Ryo Yoshinaka and Ayumi Shinohara",
note = "Funding Information: Acknowledgments. The research is supported by JSPS KAKENHI Grant Numbers JP15H05706, JP26330013 and JP18K11150, and ImPACT Program of Council for Science, Technology and Innovation (Cabinet Office, Government of Japan). Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2018.; 25th International Symposium on String Processing and Information Retrieval, SPIRE 2018 ; Conference date: 09-10-2018 Through 11-10-2018",
year = "2018",
doi = "10.1007/978-3-030-00479-8_25",
language = "English",
isbn = "9783030004781",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "311--324",
editor = "Travis Gagie and Alistair Moffat and Gonzalo Navarro and Ernesto Cuadros-Vargas",
booktitle = "String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings",
address = "Germany",
}