Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{1130263,
author = {Cabello, Sergio and Chimani, Markus and Hliněný, Petr},
address = {Sevilla},
booktitle = {XV Spanish Meeting on Computational Geometry},
howpublished = {elektronická verze "online"},
language = {eng},
location = {Sevilla},
pages = {39-42},
publisher = {Universidad de Sevilla},
title = {Computing the Stretch of an Embedded Graph},
url = {http://congreso.us.es/ecgeometry/proceedingsECG2013.pdf},
year = {2013}
}
TY - JOUR
ID - 1130263
AU - Cabello, Sergio - Chimani, Markus - Hliněný, Petr
PY - 2013
TI - Computing the Stretch of an Embedded Graph
PB - Universidad de Sevilla
CY - Sevilla
UR - http://congreso.us.es/ecgeometry/proceedingsECG2013.pdf
N2 - We provide two algorithms to compute the stretch of an embedded graph, each based on a different principle. The first algorithm is based on surgery and computes the stretch in time $O(g^4 n \log n)$ with high probability, or in time $O(g^4 n \log^2 n)$ in the worst case, where $g$ is the genus of the surface $\Sigma$ and $n$ is the number of vertices in $G$. The second algorithm is based on using a short homology basis and computes the stretch in time $O(n^2\log n + n^2g + ng^3)$.
ER -
CABELLO, Sergio, Markus CHIMANI a Petr HLINĚNÝ. Computing the Stretch of an Embedded Graph. Online. In \textit{XV Spanish Meeting on Computational Geometry}. Sevilla: Universidad de Sevilla, 2013. s.~39-42. [citováno 2024-04-24]
|
