Graph inference from a walk for trees of bounded degree 3 is NP-complete

DOI10.1007/3-540-60246-1_132zbMATH Open1193.68197OpenAlexW1601643589MaRDI QIDQ3569017FDOQ3569017

Satoru Miyano, Osamu Maruyama

Publication date: 17 June 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-60246-1_132

Recommendations

• Inferring a tree from walks
• Bounded degree graph inference from walks
• scientific article; zbMATH DE number 3878376
• Inferring a tree from walks
• Publication:4888093

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (3)

• Linear-time online algorithm for inferring the shortest path graph from a walk label
• Inferring a tree from walks
• Title not available (Why is that?)

This page was built for publication: Graph inference from a walk for trees of bounded degree 3 is NP-complete

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