Inferring a tree from walks

Osamu Maruyama, Satoru Miyano

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    1 Citation (Scopus)

    Abstract

    A walk of an edge-colored undirected graph G is a path which contains all edges in G. We show an O(n log n) time algorithm for finding the smallest tree from a walk which allows the walk. If the alphabet of colors is fixed, the algorithm runs in O(n) time. Further, we consider the problem of finding the smallest tree from partial walks, where a partial walk of G is a path in G. We prove that the problem turns to be NP-complete. We also show that inferring the smallest linear chain from partial walks is NP-complete, while the problem of inferring the smallest linear chain from a single walk is known to be solvable in polynomial time.

    Original languageEnglish
    Title of host publicationMathematical Foundations of Computer Science 1992 - 17 International Symposium, Proceedings
    EditorsIvan M. Havel, Vaclav Koubek
    PublisherSpringer Verlag
    Pages383-391
    Number of pages9
    ISBN (Print)9783540558088
    Publication statusPublished - Jan 1 1992
    Event17th Symposium on Mathematical Foundations of Computer Science, MFCS 1992 - Prague, Czech Republic
    Duration: Aug 24 1992Aug 28 1992

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume629 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other17th Symposium on Mathematical Foundations of Computer Science, MFCS 1992
    Country/TerritoryCzech Republic
    CityPrague
    Period8/24/928/28/92

    All Science Journal Classification (ASJC) codes

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint

    Dive into the research topics of 'Inferring a tree from walks'. Together they form a unique fingerprint.

    Cite this