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.
|