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

DOI10.1007/3-540-60246-1_132zbMath1193.68197OpenAlexW1601643589MaRDI QIDQ3569017

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

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)

Related Items (2)

Inferring a tree from walks ⋮ Linear-time online algorithm for inferring the shortest path graph from a walk label

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