Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Kawarabayashi, Ken-ichi | |
| dc.contributor.author | Klavík, Pavel | |
| dc.contributor.author | Mohar, Bojan | |
| dc.contributor.author | Nedela, Roman | |
| dc.contributor.author | Zeman, Peter | |
| dc.date.accessioned | 2021-06-21T10:00:09Z | - |
| dc.date.available | 2021-06-21T10:00:09Z | - |
| dc.date.issued | 2021 | |
| dc.identifier.citation | 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. | cs |
| dc.identifier.isbn | 978-1-4704-4897-4 | |
| dc.identifier.issn | 0271-4132 | |
| dc.identifier.uri | http://hdl.handle.net/11025/43672 | |
| dc.description.abstract | 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. | cs |
| dc.format | 23 s. | cs |
| dc.format.mimetype | application/pdf | |
| dc.language.iso | en | en |
| dc.publisher | American Mathematical Society | en |
| dc.relation.ispartofseries | Polytopes and Discrete Geometry | en |
| dc.rights | Plný text je přístupný v rámci univerzity přihlášeným uživatelům. | cs |
| dc.rights | © American Mathematical Society | en |
| dc.subject | Mapa grupa plocha algoritmus isomorfismus | cs |
| dc.title | Isomorphisms of maps on the sphere | en |
| dc.title.alternative | Isomorfizmy máp na sféře | cs |
| dc.type | konferenční příspěvek | cs |
| dc.type | conferenceObject | en |
| dc.rights.access | restrictedAccess | en |
| dc.type.version | publishedVersion | en |
| dc.description.abstract-translated | 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. | en |
| dc.subject.translated | Map group surface algorithm isomorphism | en |
| dc.identifier.doi | 10.1090/conm/764/15358 | |
| dc.type.status | Peer-reviewed | en |
| dc.identifier.obd | 43932853 | |
| dc.project.ID | GA20-15576S/Nakrytí grafů: Symetrie a složitost | cs |
| Appears in Collections: | Konferenční příspěvky / Conference Papers (KMA) Konferenční příspěvky / Conference papers (NTIS) OBD | |
Files in This Item:
| File | Size | Format | |
|---|---|---|---|
| conm15358.pdf | 307,76 kB | Adobe PDF | View/Open Request a copy |
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11025/43672Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.