Parameterized Algorithms on Width Parameters of Graphs
Předmětem práce je aplikování parametrizovaného přístupu k vývoji algoritmů pro různé grafové problémy. Přístup využívá tzv. parametrů k vývoji efektivních algoritmů na velmi obecných třídách grafů. Většina práce se zaměřuje na rankovou šířku jakožto relativně nový strukturální parametr. Ukazujeme,...
Uloženo v:
| Hlavní autor: | |
|---|---|
| Další autoři: | |
| Typ dokumentu: | VŠ práce nebo rukopis |
| Jazyk: | Angličtina |
| Vydáno: |
2012
|
| Témata: | |
| On-line přístup: | http://is.muni.cz/th/99352/fi_d/ |
| LEADER | 05220ctm a22007937a 4500 | ||
|---|---|---|---|
| 001 | MUB01000718869 | ||
| 003 | CZ BrMU | ||
| 005 | 20240513152206.0 | ||
| 008 | 120609s2012 xr ||||| |||||||||||eng d | ||
| STA | |a POSLANO DO SKCR |b 2020-04-29 | ||
| 035 | |a (ISMU-VSKP)158813 | ||
| 040 | |a BOD114 |b cze |d BOD018 | ||
| 072 | 7 | |a 519.1/.8 |x Kombinatorika. Teorie grafů. Matematická statistika. Operační výzkum. Matematické modelování |2 Konspekt |9 13 | |
| 072 | 7 | |a 004.4/.6 |x Programování. Software |2 Konspekt |9 23 | |
| 080 | |a 519.178 |2 MRF | ||
| 080 | |a 004 |2 MRF | ||
| 080 | |a 004.421 |2 MRF | ||
| 100 | 1 | |a Ganian, Robert |% UČO 99352 |* [absolvent FI MU] |4 dis | |
| 242 | 1 | 0 | |a Parameterized Algorithms on Width Parameters of Graphs |y eng |
| 245 | 1 | 0 | |a Parameterized Algorithms on Width Parameters of Graphs |h [rukopis] / |c Robert Ganian |
| 260 | |c 2012 | ||
| 300 | |a 143 s. | ||
| 500 | |a Vedoucí práce: Petr Hliněný | ||
| 502 | |a Dizertace (Ph.D.)--Masarykova univerzita, Fakulta informatiky, 2012 | ||
| 520 | 2 | |a Předmětem práce je aplikování parametrizovaného přístupu k vývoji algoritmů pro různé grafové problémy. Přístup využívá tzv. parametrů k vývoji efektivních algoritmů na velmi obecných třídách grafů. Většina práce se zaměřuje na rankovou šířku jakožto relativně nový strukturální parametr. Ukazujeme, že ranková šířka je velmi užitečným nástrojem k vývoji efektivních algoritmů na obecnější třídě grafů než jsou grafy s omezenou stromovou šířkou. Práce také předkládá sumarizaci a srovnání mnoha uvažovaných parametrů na orientovaných grafech. Výsledky tohoto srovnání vychází v prospěch orientované verze rankové šířky. Obsahem práce je také několik obecných výsledků o dříve uvažovaných orientovaných parametrech. Poslední část práce obsahuje řadu doplňujících vsledků, jako je např. analýza parametrizované složitosti problémů Max-Rep a Min-Rep a výhodný způsob zobecnění vrcholového pokrytí jakožto parametru k řešení velmi těžkých problémů. |% cze | |
| 520 | 2 | 9 | |a The subject of the thesis is the study of the parameterized complexity approach in developing graph algorithms. The approach allows the use of so-called parameters to obtain efficient graph algorithms on a very wide class of graphs. The thesis focuses on providing and proving algorithms for a range of graph problems, giving hardness results and proving various structural and algorithmic properties of graphs. Most of the thesis focuses on a relatively new structural parameter called rank-width. It shows that rank-width is a very powerful tool for dealing with a large number of interesting problems on graphs, including the design of efficient parameterized algorithms for many interesting problems on the large class of graphs of bounded rank-width. The thesis also provides an overview of various previously considered parameters on directed graphs and compares these to a directed version of rank-width with respect to how useful these parameters are in the design of parameterized algorith |9 eng |
| 650 | 0 | 7 | |a grafové algoritmy |7 ph770865 |2 czenas |
| 650 | 0 | 7 | |a teorie grafů |7 ph126555 |2 czenas |
| 650 | 0 | 7 | |a výpočetní technika |7 ph137273 |2 czenas |
| 650 | 0 | 7 | |a algoritmy (programování) |7 ph131788 |2 czenas |
| 650 | 0 | 9 | |a computer science |2 eczenas |
| 650 | 0 | 9 | |a algorithms |2 eczenas |
| 650 | 0 | 9 | |a computer technology |2 eczenas |
| 650 | 0 | 9 | |a graph algorithms |2 eczenas |
| 650 | 0 | 9 | |a graph theory |2 eczenas |
| 655 | 7 | |a disertace |7 fd132024 |2 czenas | |
| 655 | 9 | |a dissertations |2 eczenas | |
| 658 | |a Informatika (čtyřleté) |b Informatika |c FI D-IN4 IN (IN) |2 CZ-BrMU | ||
| 700 | 1 | |a Hliněný, Petr, |d 1971- |7 mub2013777090 |% UČO 168881 |4 ths | |
| 710 | 2 | |a Masarykova univerzita. |b Fakulta informatiky |7 kn20010709274 |4 dgg | |
| 856 | 4 | 1 | |u http://is.muni.cz/th/99352/fi_d/ |
| CAT | |c 20120609 |l MUB01 |h 0422 | ||
| CAT | |a POSPEL |b 02 |c 20120626 |l MUB01 |h 0801 | ||
| CAT | |a BATCH |b 00 |c 20130304 |l MUB01 |h 1425 | ||
| CAT | |a POSPEL |b 02 |c 20130530 |l MUB01 |h 0738 | ||
| CAT | |a POSPEL |b 02 |c 20130605 |l MUB01 |h 0736 | ||
| CAT | |a POSPEL |b 02 |c 20130821 |l MUB01 |h 1425 | ||
| CAT | |a VESELA |b 02 |c 20140314 |l MUB01 |h 1032 | ||
| CAT | |c 20140911 |l MUB01 |h 1608 | ||
| CAT | |c 20140912 |l MUB01 |h 1102 | ||
| CAT | |c 20150703 |l MUB01 |h 1205 | ||
| CAT | |c 20150901 |l MUB01 |h 1448 | ||
| CAT | |c 20150921 |l MUB01 |h 1409 | ||
| CAT | |a BATCH |b 00 |c 20151226 |l MUB01 |h 0241 | ||
| CAT | |a HANAV |b 02 |c 20160926 |l MUB01 |h 1051 | ||
| CAT | |c 20161008 |l MUB01 |h 2239 | ||
| CAT | |c 20200429 |l MUB01 |h 1338 | ||
| CAT | |c 20210614 |l MUB01 |h 0959 | ||
| CAT | |c 20210614 |l MUB01 |h 1948 | ||
| CAT | |a BATCH |b 00 |c 20210724 |l MUB01 |h 1214 | ||
| CAT | |a HANAV |b 02 |c 20211122 |l MUB01 |h 1504 | ||
| CAT | |a POSPEL |b 02 |c 20240408 |l MUB01 |h 1014 | ||
| CAT | |a VESELAX |b 02 |c 20240513 |l MUB01 |h 1521 | ||
| CAT | |a VESELAX |b 02 |c 20240513 |l MUB01 |h 1522 | ||
| CAT | |a POSPEL |b 02 |c 20241111 |l MUB01 |h 1100 | ||
| LOW | |a POSLANO DO SKCR |b 2020-04-29 | ||
| 994 | - | 1 | |l MUB01 |l MUB01 |m VYSPR |1 FI |a Fakulta informatiky |3 Diz. práce 2012 |5 42005D2622 |8 20140313 |f 72 |f Týdenní |r 20140313 |
| AVA | |a INF50 |b FI |d Diz. práce 2012 |e available |t K dispozici |f 1 |g 0 |h N |i 0 | ||