Bounded degree graph inference from walks

DOI10.1016/S0022-0000(05)80089-3MaRDI QIDQ1333403zbMATH OpenFDO

Authors Vijay Raghavan

Publication date 15 September 1994

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

edge-colored graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Graph inference from a walk for trees of bounded degree 3 is NP-complete
• Inferring a tree from walks
• Inferring a tree from walks
• Combinatorial Pattern Matching
• Inferring a graph from path frequency

Cites work

• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Complexity of automaton identification from given data
• Confluent and Other Types of Thue Systems
• Fast Pattern Matching in Strings

Cited in

(8)

• A Detachment Algorithm for Inferring a Graph from Path Frequency
• Inferring a tree from walks
• Inferring a graph from path frequency
• Graph inference from a walk for trees of bounded degree 3 is NP-complete
• Inferring a tree from walks
• Graph odometry
• Combinatorial Pattern Matching
• scientific article; zbMATH DE number 908771 (Why is no real title available?)

This page was built for publication: Bounded degree graph inference from walks

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