Mostrar el registro sencillo del ítem
Ponencia
A quadratic distance bound on sliding between crossing-free spanning trees
dc.creator | Aichholzer, Oswin | es |
dc.creator | Reinhardt, Klaus | es |
dc.date.accessioned | 2017-03-01T08:30:30Z | |
dc.date.available | 2017-03-01T08:30:30Z | |
dc.date.issued | 2004 | |
dc.identifier.citation | Aichholzer, O. y Reinhardt, K. (2004). A quadratic distance bound on sliding between crossing-free spanning trees. En 20th European Workshop on Computational Geometry, Sevilla. | |
dc.identifier.uri | http://hdl.handle.net/11441/54977 | |
dc.description.abstract | Let S be a set of n points in the plane and let TS be the set of all crossing-free spanning trees of S. We show that any two trees in TS can be transformed into each other by O(n2) local and constant-size edge slide operations. No polynomial upper bound for this task has been known, but in O.Aichholzer, F.Aurenhammer, F.Hurtado Sequences of spanning trees and a fixed tree theorem. Computational Geometry: Theory and Applications, 21(1-2):3-20, 2002. a bound of O(n2 log n) operations was conjectured. | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.relation.ispartof | 20th European Workshop on Computational Geometry (2004). | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Crossing-free spanning tree | es |
dc.subject | Local transformation | es |
dc.subject | Edge slide | es |
dc.title | A quadratic distance bound on sliding between crossing-free spanning trees | es |
dc.type | info:eu-repo/semantics/conferenceObject | es |
dc.type.version | info:eu-repo/semantics/submittedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.relation.projectID | 1/2003 | |
idus.format.extent | 4 p. | es |
dc.eventtitle | 20th European Workshop on Computational Geometry | es |
dc.eventinstitution | Sevilla | es |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
A quadratic distance bound on ... | 125.3Kb | [PDF] | Ver/ | |