Národní úložiště šedé literatury Nalezeno 7 záznamů.  Hledání trvalo 0.01 vteřin. 
Groups of automorphisms of graphs
Zeman, Peter ; Nedela, Roman (vedoucí práce) ; Felsner, Stefan (oponent) ; Širáň, Jozef (oponent)
Groups of automorphisms of graphs - abstrakt V tejto práci skúmame grupy automorfizmov špecifických tried grafov z štrukturál- neho a výpočetného hladiska. Pre intervalové, permutačné, tetivové a rovinné grafy sme odvodili induktívnu charakterizáciu grúp automorfizmov pomocou grupových súčinov. Pre chordálne grafy s ohraničenou listnatosťou sme dokázali, že problémy výpočtu grupy automorfizmov a testovania izomorfizmu sú fixed parameter tractable. Pre mapy na plochách sme popísali lineárny algoritmus, ktorý počíta grupu automorfizmov mapy na ploche s pevným rodom. 1
Algebraic, Structural, and Complexity Aspects of Geometric Representations of Graphs
Zeman, Peter ; Klavík, Pavel (vedoucí práce) ; Nešetřil, Jaroslav (oponent)
Title: Algebraic, Structural and Complexity Aspects of Geometric Representations of Graphs Author: Peter Zeman Department: Computer Science Institute Supervisor: RNDr. Pavel Klavík Supervisor's e-mail: klavik@iuuk.mff.cuni.cz Keywords: automorphism groups, interval graphs, circle graphs, comparability graphs, H-graphs, recognition, dominating set, graph isomorphism, maximum clique, coloring Abstract: We study symmetries of geometrically represented graphs. We describe a tech- nique to determine the automorphism group of a geometrically represented graph, by understanding the structure of the induced action on all geometric representations. We prove that interval graphs have the same automorphism groups as trees, and for a given interval graph, we construct a tree with the same automorphism group which answers a question of Hanlon [Trans. Amer. Math. Soc 272(2), 1982]. For permutation and circle graphs, we give an inductive characterization by semidirect and wreath prod- ucts. We also prove that every abstract group can be realized by the automorphism group of a comparability graph/poset of the dimension at most four. We also study H-graphs, introduced by Biró, Hujter, and Tuza in 1992. Those are intersection graphs of connected subgraphs of a subdivision of a graph H. This thesis is the first comprehensive...
Automorphism Groups of Geometrically Represented Graphs
Zeman, Peter ; Klavík, Pavel (vedoucí práce) ; Nedela, Roman (oponent)
V tejto práci skúmame grupy automorfizmov grafov s vel'mi silnou štruktúrou. Pravdepodobne jeden z prvých výsledkov v tomto smere je Jordanova charakterizácia triedy grúp automorfizmov stromov T z roku 1869. Prekvapivo, grupy automorfizmov prienikových grafov boli študované iba vel'mi málo. Aj pre vel'mi pochopené triedy prienikových grafov, je štruktúra ich grúp auto- morfizmov neznáma. Hlavná otázka, ktorou sa zaoberáme je, či sa z dobrej znalosti reprezentácií prienikového grafu geometrických objektov dá zrekonštruovat' jeho grupa automorfizmov. V práci skúmame hlavne intervalové grafy. Intervalové grafy sú prienikové grafy intervalov na reálnej osi. Sú jednou z naj- starších a najviac študovaných tried prienikových grafov. Náš hlavný výsledok ho- vorí, že trieda grúp automorfizmov intervalových grafov I je rovnaká ako trieda grúp automorfizmov stromov T . Navyše ukazujeme postup ako pre daný intervalový graf skonštruovat' strom s rovnakou grupou automorfizmov a tak isto obrátene, pre daný strom skonštruujeme intervalový graf. 1
Speciální třídy P-matic v intervalovém prostředí
Lorenc, Matyáš ; Hladík, Milan (vedoucí práce) ; Zeman, Peter (oponent)
Tato práce se soustředí na zobecnění některých jednoduše rozpoznatelných podtříd P- matic do intervalového prostředí spolu s některými výsledky ohledně těchto tříd. Těmito třídami jsou B-matice, doubly B-matice a BR π -matice. V této práci pro ně pak odvozujeme charakterizace, některé nutné, či postačující podmínky a navíc uvedeme i některé jejich vlastnosti, ať už uzávěrové, nebo některé podmínky na jednotlivé prvky matice, které jsou pro danou třídu splněny. Nakonec předvedeme postup, jak generovat instance některých z těchto tříd intervalových matic. 1
Circle packing and Möbius transformations
Porvichová, Janka ; Zeman, Peter (vedoucí práce) ; Kratochvíl, Jan (oponent)
Graf lze reprezentovat různými geometrickými reprezentacemi. V této práci se věnujeme reprezentaci grafů pomocí circle packingu (dotykových kružnic). Roze- bereme důležité koncepty potřebné pro dokázání klíčových výsledků ohledně této reprezentace. Představíme konkrétní známý důkaz existence circle packingu pro rovinné grafy a existence primal-dual circle packingu pro 3-souvislé grafy. Dále se budeme zabývat složitostí problému rozšíření reprezentace při zadaném čás- tečném circle packingu. Rozebereme důkaz věty, která říká, že rozhodnout, zda lze nalézt takové rozšíření, je NP-těžký problém. Představíme vlastní teoretický algoritmus pro konstrukci rozšíření založený na real RAM stroji. 1
Algebraic, Structural, and Complexity Aspects of Geometric Representations of Graphs
Zeman, Peter ; Klavík, Pavel (vedoucí práce) ; Nešetřil, Jaroslav (oponent)
Title: Algebraic, Structural and Complexity Aspects of Geometric Representations of Graphs Author: Peter Zeman Department: Computer Science Institute Supervisor: RNDr. Pavel Klavík Supervisor's e-mail: klavik@iuuk.mff.cuni.cz Keywords: automorphism groups, interval graphs, circle graphs, comparability graphs, H-graphs, recognition, dominating set, graph isomorphism, maximum clique, coloring Abstract: We study symmetries of geometrically represented graphs. We describe a tech- nique to determine the automorphism group of a geometrically represented graph, by understanding the structure of the induced action on all geometric representations. We prove that interval graphs have the same automorphism groups as trees, and for a given interval graph, we construct a tree with the same automorphism group which answers a question of Hanlon [Trans. Amer. Math. Soc 272(2), 1982]. For permutation and circle graphs, we give an inductive characterization by semidirect and wreath prod- ucts. We also prove that every abstract group can be realized by the automorphism group of a comparability graph/poset of the dimension at most four. We also study H-graphs, introduced by Biró, Hujter, and Tuza in 1992. Those are intersection graphs of connected subgraphs of a subdivision of a graph H. This thesis is the first comprehensive...
Automorphism Groups of Geometrically Represented Graphs
Zeman, Peter ; Klavík, Pavel (vedoucí práce) ; Nedela, Roman (oponent)
V tejto práci skúmame grupy automorfizmov grafov s vel'mi silnou štruktúrou. Pravdepodobne jeden z prvých výsledkov v tomto smere je Jordanova charakterizácia triedy grúp automorfizmov stromov T z roku 1869. Prekvapivo, grupy automorfizmov prienikových grafov boli študované iba vel'mi málo. Aj pre vel'mi pochopené triedy prienikových grafov, je štruktúra ich grúp auto- morfizmov neznáma. Hlavná otázka, ktorou sa zaoberáme je, či sa z dobrej znalosti reprezentácií prienikového grafu geometrických objektov dá zrekonštruovat' jeho grupa automorfizmov. V práci skúmame hlavne intervalové grafy. Intervalové grafy sú prienikové grafy intervalov na reálnej osi. Sú jednou z naj- starších a najviac študovaných tried prienikových grafov. Náš hlavný výsledok ho- vorí, že trieda grúp automorfizmov intervalových grafov I je rovnaká ako trieda grúp automorfizmov stromov T . Navyše ukazujeme postup ako pre daný intervalový graf skonštruovat' strom s rovnakou grupou automorfizmov a tak isto obrátene, pre daný strom skonštruujeme intervalový graf. 1

Viz též: podobná jména autorů
26 ZEMAN, Petr
8 Zeman, Pavel
26 Zeman, Petr
Chcete být upozorněni, pokud se objeví nové záznamy odpovídající tomuto dotazu?
Přihlásit se k odběru RSS.