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

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

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2020-04, Vol.812, p.187-202
Main Authors: Narisada, Shintaro, Hendrian, Diptarama, Yoshinaka, Ryo, Shinohara, Ayumi
Format: Article
Language:English
Subjects:
Graph inference
Palindrome
String rewriting
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2019.10.029