Linear-time online algorithm for inferring the shortest path graph from a walk label

Shintaro Narisada; Diptarama Hendrian; Ryo Yoshinaka; Ayumi Shinohara

doi:10.1016/j.tcs.2019.10.029

Linear-time online algorithm for inferring the shortest path graph from a walk label

Shintaro Narisada, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

INF - System Information Sciences

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

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.

Original language	English
Pages (from-to)	187-202
Number of pages	16
Journal	Theoretical Computer Science
Volume	812
DOIs	https://doi.org/10.1016/j.tcs.2019.10.029
Publication status	Published - 2020 Apr 6

Keywords

Graph inference
Palindrome
String rewriting

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1016/j.tcs.2019.10.029

Cite this

@article{badc8b2445f34962ac7590089d44b781,

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.",

keywords = "Graph inference, Palindrome, String rewriting",

author = "Shintaro Narisada and Diptarama Hendrian and Ryo Yoshinaka and Ayumi Shinohara",

note = "Funding Information: The research is supported by JSPS KAKENHI Grant Numbers JP15H05706 , JP26330013 and JP18K11150 , and ImPACT Program “Tough Robotics Challenge” of Japan Science and Technology Agency . Publisher Copyright: {\textcopyright} 2019 Elsevier B.V.",

year = "2020",

month = apr,

day = "6",

doi = "10.1016/j.tcs.2019.10.029",

language = "English",

volume = "812",

pages = "187--202",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - Linear-time online algorithm for inferring the shortest path graph from a walk label

AU - Narisada, Shintaro

AU - Hendrian, Diptarama

AU - Yoshinaka, Ryo

AU - Shinohara, Ayumi

N1 - Funding Information: The research is supported by JSPS KAKENHI Grant Numbers JP15H05706 , JP26330013 and JP18K11150 , and ImPACT Program “Tough Robotics Challenge” of Japan Science and Technology Agency . Publisher Copyright: © 2019 Elsevier B.V.

PY - 2020/4/6

Y1 - 2020/4/6

N2 - 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.

AB - 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.

KW - Graph inference

KW - Palindrome

KW - String rewriting

UR - http://www.scopus.com/inward/record.url?scp=85074360005&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85074360005&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2019.10.029

DO - 10.1016/j.tcs.2019.10.029

M3 - Article

AN - SCOPUS:85074360005

SN - 0304-3975

VL - 812

SP - 187

EP - 202

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Linear-time online algorithm for inferring the shortest path graph from a walk label

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this