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)

Full work available at URL https://doi.org/10.1016/S0022-0000(05)80089-3

zbMATH Keywords

edge-colored graph

Mathematics Subject Classification ID

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

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

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

Cited in

(8)

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

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)