Reconstructing Metric Trees from Order Information on Triples is NP Complete

Simple item page
dc.creatorBabson, Eric
dc.date2006-03-04
dc.date.accessioned2026-07-07T07:06:33Z
dc.date.available2026-07-07T07:06:33Z
dc.descriptionWe show that reconstructing a tree from order information on triples is NP-hard. This is in contrast to the case for ultra-metrics and for subtree information on quadruples which are both known to allow polynomial time reconstruction.
dc.identifierhttps://arxiv.org/abs/math/0603116
dc.identifierhttp://arxiv.org/abs/math/0603116
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/110066
dc.subjectCombinatorics
dc.titleReconstructing Metric Trees from Order Information on Triples is NP Complete
dc.typetext

Files

Collections

arXiv