Inferring a tree from walks

DOI10.1016/0304-3975(95)00156-5MaRDI QIDQ1351963zbMATH OpenOpenAlexFDO

Authors Osamu Maruyama, Satoru Miyano

Publication date 27 February 1997

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(95)00156-5

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Inferring a tree from walks
• Walks and paths in trees
• Walks in phylogenetic treespace
• Publication:4887809
• Reconstructing trees from traces
• Counting trees with random walks
• scientific article; zbMATH DE number 3949430
• Random walks and trees
• Tree-Walking Automata

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• A note on shortest superstrings with flipping
• Bounded degree graph inference from walks
• Complexity of automaton identification from given data
• Graph inference from a walk for trees of bounded degree 3 is NP-complete
• Linear approximation of shortest superstrings
• On finding minimal length superstrings
• On the complexity of minimum inference of regular sets
• Optimization, approximation, and complexity classes
• The minimum consistent DFA problem cannot be approximated within any polynomial

Cited in

(7)

• Inferring a graph from path frequency
• Graph inference from a walk for trees of bounded degree 3 is NP-complete
• Learning Tree Languages
• scientific article; zbMATH DE number 908771 (Why is no real title available?)
• Range and speed of rotor walks on trees
• Combinatorial Pattern Matching
• Inferring a tree from walks

This page was built for publication: Inferring a tree from walks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1351963)