Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Compatible spanning trees

Autor
Garcia, A.; Huemer, C.; Hurtado, F.; Tejel, F.
Tipus d'activitat
Article en revista
Revista
Computational geometry: theory and applications
Data de publicació
2014-07-01
Volum
47
Número
5
Pàgina inicial
563
Pàgina final
584
DOI
https://doi.org/10.1016/j.comgeo.2013.12.009 Obrir en finestra nova
Projecte finançador
Puntos y grafos: puentes geométricos (IP04 en CRP Comb. of points sets, ComPoSe,EuroGIGA ESF)
Repositori
http://hdl.handle.net/2117/26968 Obrir en finestra nova
URL
http://www.sciencedirect.com/science/article/pii/S0925772113001776 Obrir en finestra nova
Resum
Two plane geometric graphs are said to be compatible when their union is a plane geometric graph. Let S be a set of n points in the Euclidean plane in general position and let T be any given plane geometric spanning tree of S. In this work, we study the problem of finding a second plane geometric tree T' spanning S, such that is compatible with T and shares the minimum number of edges with T. We prove that there is always a compatible plane geometric tree T' having at most #n - 3#/4 edges in com...
Citació
Garcia, A. [et al.]. Compatible spanning trees. "Computational geometry: theory and applications", 01 Juliol 2014, vol. 47, núm. 5, p. 563-584.
Paraules clau
Compatible graphs, Compatible trees, Computing simple circuits, Connectivity, Embeddings, Geometric graph, Geometric spanning tree, Matchings, Plane, Segments, Set, Straight-line graphs
Grup de recerca
DCG - Discrete and Combinatorial Geometry

Participants

  • Garcia Olaverri, Alfredo Martin  (autor)
  • Huemer, Clemens  (autor)
  • Hurtado Diaz, Fernando Alfredo  (autor)
  • Tejel Altarriba, Francisco Javier  (autor)

Arxius