| Název: | Isomorphisms of maps on the sphere |
| Další názvy: | Isomorfizmy máp na sféře |
| Autoři: | Kawarabayashi, Ken-ichi Klavík, Pavel Mohar, Bojan Nedela, Roman Zeman, Peter |
| Citace zdrojového dokumentu: | KAWARABAYASHI, K., KLAVÍK, P., MOHAR, B., NEDELA, R., ZEMAN, P. Isomorphisms of maps on the sphere. In: Polytopes and Discrete Geometry. Providence: American Mathematical Society, 2021. s. 125-147. ISBN 978-1-4704-4897-4, ISSN 0271-4132. |
| Datum vydání: | 2021 |
| Nakladatel: | American Mathematical Society |
| Typ dokumentu: | konferenční příspěvek conferenceObject |
| URI: | http://hdl.handle.net/11025/43672 |
| ISBN: | 978-1-4704-4897-4 |
| ISSN: | 0271-4132 |
| Klíčová slova: | Mapa grupa plocha algoritmus isomorfismus |
| Klíčová slova v dalším jazyce: | Map group surface algorithm isomorphism |
| Abstrakt: | Hopcroft a Wong v roku 1974 navrhli lineárny algoritmus na zjišťování isomorfismu polyherálních grafů. V příspěvku navrhneme modifikovaný algoritmus na řešení tohoto problému s lineárnou složitostí. Práce obsahuje detaily nevyhnutné pro implementaci i důkaz linearity. |
| Abstrakt v dalším jazyce: | For a class of objects with a well-defined isomorphism relation the isomorphism problem asks to determine the algorithmic complexity of the decision whether two given objects are, or are not, isomorphic. Theorems by Steinitz (1916), Whitney (1933) and Mani (1971) show that the isomorphism problems for convex polyhedra, for 3-connected planar graphs, and for the spherical maps are closely related. In 1974, Hopcroft and Wong investigated the complexity of the graph isomorphism problem for polyhedral graphs. They proved that the problem can be solved in linear time. We describe a modified linear-time algorithm solving the isomorphism problem for spherical maps based on the approach by Hopcroft and Wong. The paper includes a detailed description of the algorithm including proofs. Moreover, our modified algorithm allows to determine (in linear time) the group of orientation-preserving symmetries of a spherical map. |
| Práva: | Plný text je přístupný v rámci univerzity přihlášeným uživatelům. © American Mathematical Society |
| Vyskytuje se v kolekcích: | Konferenční příspěvky / Conference Papers (KMA) Konferenční příspěvky / Conference papers (NTIS) OBD |
Soubory připojené k záznamu:
| Soubor | Velikost | Formát | |
|---|---|---|---|
| conm15358.pdf | 307,76 kB | Adobe PDF | Zobrazit/otevřít Vyžádat kopii |
Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam:
http://hdl.handle.net/11025/43672Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.