Full metadata record
| DC pole | Hodnota | Jazyk |
|---|---|---|
| dc.contributor.author | Arvind, Vikraman | |
| dc.contributor.author | Nedela, Roman | |
| dc.contributor.author | Ponomarenko, Ilia | |
| dc.contributor.author | Zeman, Peter | |
| dc.date.accessioned | 2022-12-19T11:00:10Z | - |
| dc.date.available | 2022-12-19T11:00:10Z | - |
| dc.date.issued | 2022 | |
| dc.identifier.citation | ARVIND, V. NEDELA, R. PONOMARENKO, I. ZEMAN, P. Testing Isomorphism of Chordal Graphs of Bounded Leafage is Fixed Parameter Tractable. In Lecture Notes in Computer Science. Cham: Springer, 2022. s. 29-42. ISBN: 978-3-031-15913-8 , ISSN: 0302-9743 | cs |
| dc.identifier.isbn | 978-3-031-15913-8 | |
| dc.identifier.issn | 0302-9743 | |
| dc.identifier.uri | 2-s2.0-85140764930 | |
| dc.identifier.uri | http://hdl.handle.net/11025/50747 | |
| dc.description.abstract | Určit algoritmickou složitost problému isomorfizmu grafů je jeden z nejdůležitejších otevřených problémů teoretické informatiky. Je známé, že testování isomorfizmu chordálních grafů je polynomiálně ekvivalentní obecnému problému isomorfizmu grafů. Každý chordální graf může být reprezentován jako průnikový graf množiny podstromů nějakého stromu T. Minimální počet listů T, v kterém je možné chordální graf G reprezentovat, se nazývá listnatost G. V našem příspěvku dokážeme, že existuje FPT algoritmus pro grafový izomorfizmus chordálních grafů s ohraničenou listnatostí. | cs |
| dc.format | 14 s. | cs |
| dc.format.mimetype | application/pdf | |
| dc.language.iso | en | en |
| dc.publisher | Springer | en |
| dc.relation.ispartofseries | Lecture Notes in Computer Science | en |
| dc.rights | Plný text je přístupný v rámci univerzity přihlášeným uživatelům. | cs |
| dc.rights | © Springer | en |
| dc.title | Testing Isomorphism of Chordal Graphs of Bounded Leafage is Fixed Parameter Tractable | en |
| dc.title.alternative | Testování isomorfizmu chordálních grafů s ohraničenou listnatostí je "fixed parameter traceable" | cs |
| dc.type | ConferenceObject | en |
| dc.rights.access | restrictedAccess | en |
| dc.type.version | publishedVersion | en |
| dc.description.abstract-translated | The computational complexity of the graph isomorphism problem is considered to be a major open problem in theoretical computer science. It is known that testing isomorphism of chordal graphs is polynomial-time equivalent to the general graph isomorphism problem. Every chordal graph can be represented as the intersection graph of some subtrees of a representing tree, and the leafage of a chordal graph is defined to be the minimum number of leaves in a representing tree for it. We prove that chordal graph isomorphism is fixed parameter tractable with leafage as parameter. | en |
| dc.subject.translated | chordal graph | en |
| dc.subject.translated | graph isomorphism | en |
| dc.subject.translated | algorithmic complexity | en |
| dc.identifier.doi | 10.1007/978-3-031-15914-5_3 | |
| dc.type.status | Peer-reviewed | en |
| dc.identifier.obd | 43937101 | |
| dc.project.ID | GA20-15576S/Nakrytí grafů: Symetrie a složitost | cs |
| Vyskytuje se v kolekcích: | Konferenční příspěvky / Conference papers (NTIS) OBD | |
Soubory připojené k záznamu:
| Soubor | Velikost | Formát | |
|---|---|---|---|
| tubingenproceedings.pdf | 10,73 MB | 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/50747Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.