V letním semestru 2013/14 má kód BI-TS2 (případně MI-TS2) a koná se každou Středu od 14:30 v místnosti TH:A-1242, tedy na dvanáctém patře budovy A.
Seminář vedou společně Ondřej Suchý a Tomáš Valla.
Chcete-li nás kontaktovat, napište na email ondrej.suchy@fit nebo tomas.valla@fit (místo @fit doplňte @fit.cvut.cz).
Program semináře
Dne 14.5.2014 (Rektorský den) představí Lukáš Prokop článek Strategic Multiway Cut and Multicut Games jehož autory jsou Elliot Anshelevich, Bugra Caskurlu a Ameya Hate.
Minulý program
Dne 19.2.2014 se představovali a rozdělovali články. Také proběhlo přivítání s novými tvářemi.
Dne 26.2.2014 představil Jakub Puchýř článek Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms jehož autory jsou Yang Liu, Songjian Lu, Jianer Chen a Sing-Hoi Sze.
Dne 5.3.2014 představil Jan Strnad článek Finding the smallest binarization of a CFG is NP-hard jehož autorem je Carlos Gómez-Rodríguez.
Dne 12.3.2014 představil Ondřej Fiedler článek Online Coloring of Bipartite Graphs with and without Advice jehož autory jsou Maria Paola Bianchi, Hans-Joachim Böckenhauer, Juraj Hromkovič a Lucia Keller.
Dne 19.3.2014 představil Jakub Doubek článek Two-color Babylon jehož autory jsou Agelos Georgakopoulos a Peter Winkler.
Dne 26.3.2014 představil Josef Malík článek Picture-Hanging Puzzles jehož autory jsou Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest a Mihai Patraşcu.
Dne 2.4.2014 představil Adam Kučera článek On the Maximum Density of Graphs with Unique-Path Labellings jehož autory jsou Abbas Mehrabian, Dieter Mitschey a Pawel Pralat.
Dne 9.4.2014 představil Robin Obůrka článek Overhang jehož autory jsou Mike Paterson a Uri Zwick.
Dne 23.4.2014 představil Roman Jelínek článek A comprehensive study of an online packet scheduling algorithm jehož autorem je Fei Li.
Dne 30.4.2014 představil Stanislav Zubal článek Gaming Is a Hard Job, but Someone Has to Do It! jehož autorem je Giovanni Viglietta.
Dne 7.5.2014 představil Jan Cejhon článek Infinite Connect-Four Is Solved: Draw jehož autory jsou Yoshiaki Yamaguchi, Kazunori Yamaguchi, Tetsuro Tanaka a Tomoyuki Kaneko.
Vida Dujmović, Daniel J. Harvey, Gwenaël Joret, Bruce Reed, and David R. Wood: A Linear-Time Algorithm for Finding a Complete Graph Minor in a Dense Graph
Novy jeste rychlejsi algoritmus pro nalezeni minoru (neco jako podgraf) v hustem grafu. Asi potreba doplnit uvodem do toho, co je to minor. PDFPDF
Vladimir I. Benediktovich: On rational approximation of a geometric graph
Geometrický graf je nakreslení grafu do roviny pomocí úseček bez křížení.
Geometrický graf je racionální, pokud jsou všechny délky úseček racionální čísla.
Otázka zní, u jakých grafů lze perturbovat pozice vrcholů tak, aby byl
graf racionální a aby všechny vrcholy měly zároveň racionální souřadnice.
Článek dává kladnou odpověď pro jistou třídu grafů. PDF
Heidi Gebauer: On the construction of 3-chromatic hypergraphs with few edges
Slavný problém v kombinatorice se ptá, kolik minimálně musí být číslo m(N)
tak, aby šlo zkonstruovat hypergraf na N vrcholech s m(N) hranami,
který je 3-barevný. V článku se ukazuje nový horní odhad na číslo m(N). PDF
Weigen Yan: On the number of spanning trees of some irregular line graphs
Pro graf G dává smysl počítat, kolik různých koster obsahuje,
a pro speciální třídy grafů existují i explicitní vzorce pro tyto počty.
Článek studuje počet koster line-grafu od grafu G, který není regulární.
(Line-graf vznikne prohozením pojmů vrchol a hrana.) PDF
Leah Epstein, Michal Feldman, Tami Tamir, Lukasz Witkowski, Marcin Witkowski: Approximate strong equilibria in job scheduling games with two uniformly related machines
Problém rozvrhování úkolů ke zpracování na paralelně běžící stroje má mnoho variant
a je studován v různých kontextech.
V článku se uvažuje konkurenční prostředí, kdy jednotlivé úkoly platí za to,
aby byly zpracovány, nicméně cena se odvíjí od nabídky a poptávky.
Každý úkol chce být zpracován, ale zároveň na tom chce co nejvíc ušetřit.
Ukazují se vlastnosti ekvilibrií této hry. PDF
Vladimir G. Deineko, Gerhard J. Woeginger: Two hardness results for core stability in hedonic coalition formation games
Téma z klasické teorie her: hráči se stávají členy koalic, za což jsou nějak
odměňováni. Odměna hráče se odvíjí pouze od toho, s kým jsou v koalici,
a nezávisí na hráčích mimo koalici. Otázka zní, zda je daný stav této
hry stabilní, tedy zda žádný hráč nechce změnit koalici.
Článek ukazuje NP-úplnost této otázky. PDF
Daniel W. Cranston, William B. Kinnersley, Suil O, Douglas B. West: Game matching number of graphs
Dva hráči vybírají hrany grafu, aby průběžně tvořily párování.
Jeden hráč se snaží vyrobit co největší párování, druhý co nejmenší.
Jak hra dopadne? Článek dává odpověď. PDF
Toufik Mansour, Mark Shattuck: A combinatorial approach to a general two-term recurrence
Článek studuje metody řešení jistého speciálního typu
lineárních dvojitě rekurzivně definovaných posloupností. PDF
R.D. Malikiosis, M. Matolcsi, I.Z. Ruzsa: A note on the pyjama problem
Uvažme sadu vertikálních proužků v rovině, kde střed proužků leží na
celočíselných bodech osy x. Otázka zní, kolik musím sjednotit rotací,
abych pokryl těmito množinami celou rovinu.
Pro dostatečně široké proužky jich stačí konečně mnoho, pro příliš
úzké už je jich třeba nekonečně. PDF
Shi-Mei Ma: Some combinatorial arrays generated by context-free grammars
Článek ukazuje, že některé kombinatorické posloupnosti, například
Catalanův trojúhelník, lze vygenerovat bezkontextovou gramatikou. PDF
Máté Matolcsi, Imre Z. Ruzsa: Sets with no solutions to x + y = 3z
Jak velká je množina A\subset [0,1], jejíž prvky
řeší rovnici x+y=3z? Bude třeba nastudovat pojmy okolo Lebesgueových měr. PDF
Ming Liu, Feifeng Zheng, Shijin Wang, Yinfeng Xu: Approximation algorithms for parallel machine scheduling with linear deterioration
Článek studuje několik metod, jak rozvrhovat úlohy na paralelní počítače,
aby se minimalizoval čas zpracování všech úloh.
U metod analyzuje jejich aproximační faktor. PDF
Takuya Umesato, Toshiki Saitoh, Ryuhei Uehara, Hiro Ito, Yoshio Okamoto: The complexity of the stamp folding problem
Něco pro milovníky origami: chceme ohýbat papír tak, aby počet vrstev
papíru mezi každou dvojicí ohýbaných částí je minimální.
Studuje se výpočetní složitost problému. PDF
Pär Kurlberg, Jeffrey C. Lagarias, Carl Pomerance: On sets of integers which are both sum-free and product-free
Množina přirozených čísel M je součtuprostá a násobkuprostá,
pokud pro každé dvě x,y \in M neleží x+y a x.y v M.
Článek studuje maximální hustotu takových množin. PDF
John M. Freeman, Tomas Schonbeki, Wandi Wei: On the tennis ball problem
Dostali jsme dva míčky, z nich jeden vybereme a odhodíme.
Dostaneme další dva, máme tedy tři, z nichž jeden opět odhodíme.
A tak dále. Otázka je, kolik je všech tímto způsobem vyrobitelných
posloupností odhozených míčků. Článek studuje zobecnění tohoto problému. PDF
András Csernenszky, Ryan R. Martin, András Pluhár: On the complexity of chooser-picker positional games
Dva hráči zabírají střídavě prvky množiny, nad kterou jsou
definovány vyhrávající podmnožiny
kdo obsadil nějakou z nich, vyhrál.
Uvažme variantu, kdy jeden hráč vybere dva prvky a druhý hráč určí,
který prvek z těch dvou komu připadne.
Článek ukazuje výpočetní složitost problému určit, kdo danou hru vyhraje. PDF
Fraser Stewart: Pirates and treasure
Na grafu jsou dvě konkurenční party pirátu, kteří na střídačku
chodí po vrcholech a sbírají na nich poklady.
Otázka je, kdo v této hře je schopen nasbírat větší poklad.
Článek studuje strukturu této hry a její výpočetní složitost. PDF
Herbert Fleischner: Uniquely Hamiltonian Graphs of Minimum Degree 4
Článek konstruuje nekonečnou rodinu grafů s jistými požadavky
na stupně vrcholů, které obsahují právě jednu hamiltonovskou kružnici. PDF
Luke Postle: Pebbling Graphs of Fixed Diameter
Pebbling na grafu je solitér, kdy jsou na vrcholech rozmístěny kamínky
a tah spočívá v tom, že se z vrcholu vezmou dva, jeden zahodí a druhý
přemístí na nějaký sousední vrchol. Otázka je, kolik minimálně
potřebuje kamínku, aby pro libovolné počáteční rozmístění šlo
dopravit kamínek do nějakého cílového vrcholu.
Článek podáva nový horní odhad. PDF
Pierre Aboulker: Excluding 4-Wheels
4-kolo je kružnice plus vrchol napojený na kružnici čtyřmi hranami.
Článek ukazuje, že každý graf neobsahujíci 4-kolo jako podgraf
je vrcholově 4-obarvitelný. PDF
Hongliang Lu, David G. L. Wang, and Qinglin Yu: On the Existence of General Factors in Regular Graphs
Ukazuje se za jakych podminek ma nebo nema regularni graf faktor se stupni z dane mnoziny. PDF
Graham Brightwell and Mareike Massow: Diametral Pairs of Linear Extensions
Kolik maximalne prvku muzou radit ruzne dve linearni rozsireni daneho castecneho usporadani. Ukazuje se NP-uplnost a vyvraci starsi domnenka na to jak takova rozsireni vypadaji. Delsi, asi by nebyl problem neco vybrat. PDF
Sariel Har-Peled and Bernard Lidicky: Peeling the Grid
Rozebirame mrizku n x n tak, ze vzdy obereme vrcholy konvexniho obalu totho, co nam zbyva. Ukazuje se, ze to jde prekvapive rychle. Kratsi. PDF
Noga Alon, Erik D. Demaine, MohammadTaghi Hajiaghayi, Tom Leighton: Basic Network Creation Games
Mame graf a kazdy vrchol se ho snazi vylepsit tim, ze vzdy prepoji jednu hranu tak, aby zlepsil svoji vzdalenost od ostatnich. Jak dobre to v globalu dopadne, az se to ustali? Ukazuji se horni a dolni meze. PDF
Balázs Keszegh, János Pach, Dömötör Pálvölgyi: Drawing planar graphs of bounded degree with few slopes
Kresli se graf do roviny, tak aby hrany pouzivali co nejmene ruznych uhlu (smernic). Ukazuje se, ze pocet potrebnych uhlu lze omezit nejvyssim stupnem grafu a pokud povolime na kazde hrane jeden zlom, vyjde i hezka mez. PDF
Sam Buss,Michael Soltys: Unshuffling a square is NP-hard
Retezec je mixem dvou retezcu, pokud vznikne prokladanim pismenek z tech dvou retezcu tak, ze zustanou v puvodnim poradi (jako pri michani karet).
Ukazuje, ze je NP-tezke rozhodnout, zda dany string vznikl smichanim nejakeho retezce sama se sebou. PDF
Telikepalli Kavitha: Dynamic Matrix Rank with Partial Lookahead
Jak si prubezne udrzovat hodnost matice ktera se meni. Dosahuji amortizovane O(n^{w-1}) na zmenu, ale potrebuji znat co se bude priste menit (neni potreba vedet jak). PDF
Dominik Gall, Riko Jacob, Andrea Richa, Christian Scheideler, Stefan Schmid, Hanjo Täubig: A Note on the Parallel Runtime of Self-Stabilizing Graph Linearization
Zkouma se jak narovnat graf na primku pomoci jednoduchych lokalnich ooperaci iniciovanych primo vrcholy. Netrivialne se analyzuje nekolik scenaru a algoritmu. PDF
Helmut Alt, Esther M. Arkin, Alon Efrat, George Hart, Ferran Hurtado, Irina Kostitsyna, Alexander Kröller, Joseph S. B. Mitchell, Valentin Polishchuk: Scandinavian Thins on Top of Cake: New and Improved Algorithms for Stacking and Packing
Jak velky kufr potrebujeme, abychom do nej mohli nandat vsechny zadane veci (pokud je smime/nesmime otacet apod.). NP-tezkost, trocha geometrie, PTAS, ilustrovane. PDF
Stefan Dobrev, Lata Narayanan, Jaroslav Opatrny: Optimal Sensor Networks for Area Monitoring Using Rotating and Beam Sensors
Monitorovani prostoru pomoci statickych a otocnych pohybovych cidel. Jak sestavit sit s nejmensim poctem cidel? Ilustrovano. PDF
Timothy M. Chan, Stephane Durocher, Kasper Green Larsen, Jason Morrison, Bryan T. Wilkinson: Linear-Space Data Structures for Range Mode Query in Arrays
Je zadano pole a stavi se struktura, ktera umi efektivne odpovidat na dotazy typu: Ktera hodnota se vyskytuje mezi indexy i a j nejcasteji? Mozna bude potreba nacist i neco z odkazovane literatury, nejspis by stacila ta staticka struktura. PDF
Johan M. M. van Rooij, Marcel E. van Kooten Niekerk, Hans L. Bodlaender: Partition Into Triangles on Bounded Degree Graphs
Cilem je rozdelit graf na vrcholove disjunktni trojuhelniky. Ukzauje se, ze je to linerane resitelne pro grafy stupne 3 a NP-uplne pro grafy stupne 4. Dale se ukazuje rychly exponencialni algoritmus pro grafy stupne 4, ten je asi nejzajimavejsi. Delsi. PDF
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk: Solving the 2-Disjoint Connected Subgraphs Problem Faster than 2^n
Mame dany dve mnoziny vrcholu a hledame rozdeleni vsech vrcholu grafu na dve mnoziny tak, aby byly souvisle a kazda z nich obsahovala jednu ze zadanych mnozin. V clanku je 1.93^n algoritmus pro tenhle problem, prvni ktery prolomil 2^n. Dlasi vysledky mozno vynechat. PDF
Jean-François Couturier, Petr A. Golovach, Dieter Kratsch, Daniël Paulusma: List Coloring in the Absence of a Linear Forest
Ukazuje se, ze rozhodnout, zda lze graf obarvit k barvami lze v polynomialnim case pro grafy, ktere neobsahuji urcite lesy jako indukovany podgraf. PDF
Anil Maheshwari, Jörg-Rüdiger Sack, Kaveh Shahbaz, Hamid Zarrabi-Zadeh: Improved Algorithms for Partial Curve Matching
Mame zadanou malou a velkou krivku a otazka zni, jestli ta vetsi obsahuje cast podobnou te mensi. Ukazuje se O(nm) algoritmus pomoci zajimave datove struktury, kde n a m jsou pocty segmentu v tech krivkach. PDF
Romeo Rizzi, David Cariolaro: Polynomial Time Complexity of Edge Colouring Graphs with Bounded Colour Classes
Barveni hran grafu minimalnim poctem barev tak, ze (dve sousedni hrany nejsou obarveny stejnou barvou a) kazda barva je pouzita pouze nekolikrat. Polynomialni algoritmus, kratsi, ale spoleha na starsi algoritmy, ktere by asi bylo dobre nastudovat. PDF
Keren Cohen, Raphael Yuster: On Minimum Witnesses for Boolean Matrix Multiplication
Matice svedku pri nasobeni booleovskych matic je matice indexu, ktere dokazuji, ze to prislusne policko ma byt jedna. Ukazuji se rychle algoritmy pro vypocet takove matice svedku. PDF
Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch, Charis Papadopoulos, Yngve Villanger: Enumerating Minimal Subset Feedback Vertex Sets
Hleda se mnozina vrcholu grafu, ktera prerusi vsechny cykly v nejake dane podmozine vrcholu. Ukazuje se, jak najit vsechny takove mnoziny v case 1.8^n. K analyze se vyuziva velmi jednoducha Measure and Conquer. PDF
Giovanni Viglietta: Lemmings is PSPACE-complete
Ukzauje se, ze znama hra Lemmings, je (za urcitych podminek) PSPACE-uplna. PDF
Arash Asadpour, Uriel Feige, Amin Saberi: Santa Claus Meets Hypergraph Matchings
Santa Claus rozdeluje darecky ktere maji ruznou cenu pro ruzne deti a snazi se to udelat tak, aby vsechny deti dostali co nejvic. Ukazuje se vylepseny approximacni algoritmus, zalozeny na LP a lokalnim vyhledavani. Prevdepodobne narocne, i kdyz nijak dlouhe. PDF
Jesse Stern: Spider Solitaire is NP-Complete
Aneb jak vyuzit vasi babicku :-) PDF
Graham: Fault-free Tilings of Rectangles
Vyplnovani obdelniku obdelnicky tak, aby zadna spara nebyla skrz. PDF
Chung, Gilbert, Graham, Shearer, van Lint: Tiling Rectangles with Rectangles
Zkouma se pokryvani obdelniku obdelnicky takove, ze neexistuje netrivialni podobdelnicek, jehoz hrany by vsechny byli sparami. PDF
Laurent Bulteau, Guillaume Fertin, Irena Rusu: Pancake Flipping Is Hard
Otaceni palacinek tim, ze se do hromady palacinek nekam zapichne obracecka a vse nad ni se obrati. Cilem je je setridit aby nejvetsi byla dole. Ukazuje se NP-tezkost.
PDF
Sergio Cabello, Jean Cardinal, Stefan Langerman: The Clique Problem in Ray Intersection Graphs
Uvazme graf, kde kazdemu vrcholu odpovida poloprimka v rovine a dva vrcholy jsou sousedy, pokud se poloprimky protinaji. Ukazuje se, ze kazdy takovy graf je komplementem nejakeho sudeho podrozdeleni rovinneho grafu. V dusledku toho je klika v takovych grafech tezka. PDF
Rani Hod, Alon Naor: Component Games on Regular Graphs
Studuji se hry na grafech, kdy si dva hraci stridave berou hrany. Jeden se snazi ze svych hran vytvorit velkou komponentu a druhy mu brani. Ukazuje se kdo kdy zvitezi na d-regularnich grafech. PDF
Tomasz Krawczyk, Arkadiusz Pawlik, And Bartosz Walczak: Coloring Triangle-Free Rectangular Frame Intersection
Graphs with O(log log n) Colors
Graf, kde vrcholy jsou (prazdne) obdelniky rovnobezne s osami a jsou spojene hranou pokud se protinaji, lze obarvit O(log log n) barvami. Pouzivaji se netrivialni vysledky odjinud, ale snad je nejaka myslenka i tady. PDF
Brendan D. McKay, Adolfo Piperno: Practical graph isomorphism, II
Souhrn jak se dnes resi grafovy isomorfismus. Mozna bude tezke najit neco rozumneho, co by se dalo odprezentovat. PDF
Dmitriy Nuriyev: A DP Approach to Hamiltonian Path Problem
Netrivialni "polynomialni" algoritmus resici tento NP uplny problem. Jde o to najit chybu. Mozna spise pro nekoho, kdo nechce prezentovat? PDF
el Houcein el Abdalaoui, Mohamed Dahmoune, and Djelloul Ziadi: On the transition reduction problem for finite
automata
Jde o to minimalizovat konecny automat, tentokrate nikoliv co do poctu stavu, nybrz co do poctu prechodu. PDF
Benjamin Doerr, Anton Eremeev, Frank Neumann, Madeleine Theile, Christian Thyssen: Evolutionary Algorithms and Dynamic
Programming
Srovnani DP a evolucnich algoritmu a jak prevadet jedno na druhe. Hodne dlouhe a asi ne moc presentovatelne. PDF
Guillaume Bonfante, Florian Deloup: The genus of regular languages
Rod grafu je (zjednodusene receno) pocet usi, ktere musim pridat kouli, abych na ni mohl nakreslit tento graf bez krizeni. Zkoumaji se regularni jazyky podle rodu grafu jejich automatu. Pomerne dlouhe a mozna slozite pro nekoho kdo se zatim moc nesetkal s topologii. PDF
Richard Southwell and Chris Cannings: Best Response Games on Regular Graphs
Hry v socialnich sitich kdy kazdy hrac nejakym zpusobem reaguje na chovani ostatnich. Trochu nejasne, co se vlastne dela, prevadi se to na deleni mnohodimenzionalniho prostoru... Celkem dlouhe, mozna by se z toho dalo neco vybrat. PDF
Artur Jeż: Approximation Of Grammar-Based Compression Via Recompression
Linearni algoritmus, ktery vystoupi malou bezkontextovou gramatiku, ktera vygeneruje vstupni retezec. Jen o logaritmus vetsi, nez velikost nejmensi takove.
Takove algoritmy byly znamy, ale tenhle je pry "jednoduchy s jednoduchou analyzou". PDF
Amy Glen and Jamie Simpson: The Total Run Length of a Word
Beh ve slove je jeho periodicke podslovo o delce aspon dvou jeho period. Ukazuji se odhady na soucet delek vseh behu ve slove dane delky. PDF
Mohsen Ghaffari, Bernhard Haeupler, Majid Khabbazian: A Bound on the Throughput of Radio Networks
Studuje se model radiovych siti, kde v kazdem kole kazde AP bud vysila, nebo prijima a prijme prave tehdy kdyz vysila prave jeden z jeho sousedu. Cilem je distribuovat k zprav po grafu, aby se je dozvedel kazdy. Predstavuje se sit s malym diametrem, ktera potrebuje hodne kol. Potreba trochu pravdepodobnosti. PDF
Vida Dujmovic: Graph Layouts via Layered Separators
Ukazuji se vylepsene odhady na tzv. trackove a frontove cislo planarnich grafu. V obou pripadech se nejak radi vrcholy a rodeluji se hrany nebo vrcholy do skupin tak, ze hrany (v jedne skupine) respektuji poradi vrcholu - nekrizi se. PDF
Michal Adamaszek: The Smallest Nonevasive Graph Property
Vlastnost je "tekava", pokud se kazdy algoritmus, ktery ji testuje musi v nejhorsim pripade zeptat na existenci kazde hrany. Vetsina vlastnosti takovych je, ukazuje se jedna na 5-i vrcholech, ktera takova neni. Velmi kratke a jednoduche. PDF
Igor Pak And Jed Yang: Tiling Simply Connected Regions With Rectangles
Vi se, ze dlazdeni obecneho utvaru dvema obdelniky je tezke, kdezto dlazdeni jednodusse souvisleho utvaru dvema obdelniky je jednoduche. Ukazuje se, ze dlazdeni jedn. souv. utv. miliony obdelniku je tezke. Mozna by bylo zajimave nastudovat i ten znamy algoritmus, ale to uz by asi bylo moc dlouhe. PDF
A. Ahadia, A. Dehghan: The Complexity of the Proper Orientation Number
Orientace grafu je vlastni, pokud kazde dva sousedni vrcholy maji v teto orientaci jiny vystupni stupen. Minimalizuje se potrebny vystupni stupen. Ukazuje se NP-tezkost pro rovinne a 4-regularni grafy a poly algortimus pro 3-regularni. PDF
Alejandro Erickson and Frank Ruskey: Domino Tatami Covering is NP-complete
DLazdi se pravouhly utvar pomoci kostek domina tak, aby se zadne 4 kostky nepotkali v jednom bode. Ukazuje se NP-uplnost a jeji dusledky pro hledani specialniho parovani v jistych grafech PDF
Hai-Jun Zhou: The Feedback Vertex Set Problem: a Spin Glass Approach
V problemu jde o to najit mnozinu vrcholu, ktera protina vsechny cykly grafu, a je NP-uplny. Zavadi se nejaky "spin glass" model, ktery prevadi vyse uvedenou globalni pominku na lokalni pro kazdou hranu. Ten se resi pomoci bilief propagation a ukazuje se, ze to dava dobrou aproximaci. Zni to komplikovane. PDF
Patrizio Angelini, Fabrizio Frati, Maurizio Patrignani, Vincenzo Roselli: Morphing Planar Graph Drawings Efficiently
Hleda se spojita transformace mezi dvema rovinnymi useckovymi nakreslenimi grafu. Ukazuje se, ze takova transformace se da rozdelit O(n^2) casti, z nichz kazda je linearni, coz vylepsuje starsi vysledky. Snad ta myslenka neni moc skryta v referencich. PDF
Brešar, Klavžar, Rall: Domination game played on trees and spanning subgraphs
Dominator a Prodluzovac hraji hru na grafu: stridave vybiraji vrcholy tak,
aby vybrana mnozina dominovala aspon o 1 vrchol vic nez v predchozim tahu.
Dominator se snazi hru ukoncit co nejdrive, Prodluzovac ji prodluzuje.
Otazka je, na jak dlouho obema hracum jejich strategie vydrzi.
Clanek to studuje pro stromy a kostry grafu.
PDF
Axenovich, Osang: Unavoidable subtrees
Uvazme mnozinu M vsech stromu na K vrcholech.
Kolik minimalne vrcholu N potrebuju, aby libovolny strom T na N vrcholech
obsahoval aspon jeden strom z M jako podstrom?
PDF
Palbom: Complexity of the directed spanning cactus problem
Kaktus K je podgraf grafu G, ktery je silne souvisly orientovany graf,
jeho kazda hrana je obsazena v prave jednom cyklu, a spojuje
vsechny vrchol z G.
Clanek studuje vypocetni slozitost hledani kaktusu v zadanem grafu.
PDF
Meeks, Scott: The complexity of flood-filling games on graphs
Clanek studuje kombinatorickou hru Free-Flood-It, kde se hraci
minimalni poctem tahu "flood-fill" snazi udelat barevny hraci plan
jednobarevny.
PDF
Shao, Chao: Recursive method to solve the problem of "Gambling with God"
Co se stane, kdyz chci hrat hazardni hru s vsemocnym bohem? :-)
PDF
Brimkov, Leach, Wu, Mastroianni: Approximation algorithms for a geometric set cover problem
Kdyz mame na vstupu mnozinu usecek v rovine, existuje
mala mnozina bodu, ktera protina vsechny zadane usecky?
Rozhodnout tento problem je vypocetne obtizne, clanek tedy zkouma
aproximacni pristupy.
PDF
Demange, Stefano, Leroy-Beaulieu: On the online track assignment problem
Jak studovat vypravovani vlaku pomoci barveni grafu?
PDF
Hoang, Kaminski, Sawada, Sritharan: Finding and listing induced paths and cycles
Jak efektivne hledat a vypsat vsechny indukovane cesty v grafu?
PDF
Anily, Pfeffer: The uncapacitated swapping problem on a line and on a circle
Mame graf s vyznacenymi zdrojovymi a cilovymi vrcholy se zbozim,
a mame autickem povymenovat zbozi na nich tak, aby najelo minimalni trasu.
To je obecne NP-tezke. Clanek ukazuje polynomialni algoritmy pro
line grafy a circle grafy.
PDF
Feldheim, Hod: 3/2 firefighters are not enough
Na grafu vypukl ohen, ktery se siri do sousednich vrcholu.
Kolik hasicu potrebujeme, abychom pozar uhasili na rovinne mrizce?
PDF
Kabadi, Punnen: Spanning cactus of a graph: Existence, extension, optimization, and approximation
Clanek studuje vypocetni slozitost hledani kaktusu v grafu.
PDF
Campos, Wakabayashi: On dominating sets of maximal outerplanar graphs
Ukazuje se horni odhad na dominanci maximalniho vnejskove rovinneho grafu,
pricemz tento odhad nakonec vyjde jako optimalni.
PDF
Durocher, He, Munro, Nicholson, Skala: Range majority in constant time and linear space
Clanek popisuje datovou strukturu, ktera umi v O(1) zodpovidat tyto dotazy:
je dano pole, dotaz je na interval, pro ktery se ma vratit prevladajici
prvek v tomto intervalu.
PDF
Thorup: All Structured Programs Have Small Tree Width and Good Register Allocation
Alokace registru pri prekladu urcitych programovacich jazyku je vlastne
ekvivalentni obarveni jisteho specialniho grafu. V clanku se ukazuje, ze pokud
ma graf omezenou stromovou sirku, zvladneme problem rozumne aproximovat.
Specialne, jazyky bez nepodmineneho skoku maji stromovou sirku maximalne 6
a lze tedy rozvrzeni registru 4-aproximovat.
PDF
Cornelsen, Stefano: Track assignment
Jak vyresit problem vlakoveho jizdniho radu pomoci barveni grafu?
Studujeme pro urcite specialni tridy jizdnich radu.
PDF
Raphael Yuster: Maximum Matching in Regular and Almost Regular
Graphs
Ukazuje se algoritmus pro hledani maximalniho parovani v grafech, jejichz minimalni a maximalni stupen se lisi jen o malo. V nekterych pripadech rychlejsi nez zname algoritmy pro obecne grafy. PDF
Lijun Chang, Jeffrey Xu Yu, Lu Qin: Fast Maximal Cliques Enumeration in Sparse Graphs
Cilem je vypsat vsechny kliky v ridkem grafu tak, aby se na kazdou dalsi cekalo jen na polynomialni cas. Polynom zavisi jen na stupnich grafu, nikoliv na jeho velikosti. PDF
Jessica Muntza, Sivaram Narayana, Noah Streibb, Kelly Van Ochtena: Optimal pebbling of graphs
Klasicka hra na grafu. Kdyz sundame dva kaminky z jednoho vrcholu muzeme polozit jeden na souseda. Kolik musime mit na zacatku kaminku (libovolne rozlozenych), chceme-li mit na konci na kazdem vrcholu aspon jeden? Ukazuji se horni a dolni meze pro grafy polomeru d. PDF
Bernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan: Rank-Pairing Heaps
Haldy, ktere jsou stejne rychle jako Fibonacciho, ale na delete potrebuji jen jeden cut. PDF,PDF
Torben Hagerup: An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees
Pro dany strom s vahami na hranach a seznam paru vrcholu toho stromu je treba pro kazdy par urcit nejtezsi hranu na ceste mezi nimi. Linearni algoritmus se znal, tenhle je jednodussi. Lze pouzit k overeni, ze strom je skutecne nejlehci kostrou grafu. Implementace v Dcku. PDF
Antoni Lozano, Merce Mora, Carlos Seara: Distinguishing trees in linear time
Graf je d-odlisitelny, pokud existuje ocislovani jeho vrcholu pomoci {1, ..., d}, ktere je zachovano jen identitou. Clanek obsahuje linearni algoritmus pro urceni nejmensiho d-odlisujiciho cisla pro lesy. Mozna dost zavisi na predchozich O(n log n) algoritmech. PDF
Saieed Akbari, Vahid Liaghat, Afshin Nikzad: Colorful Paths in Vertex Coloring of Graphs
Ukazuje se, ze v grafu obarvenem delta+1 barvami, existuje pro kazdy vrchol cesta, ktera v nem zacina a obsahuje prave jeden vrchol kazde barvy. PDF
Mikkel Thorup: Undirected Single Source Shortest Path in Linear Time
Prvni, ktery toho dosahuje deterministicky. Preklada, ze vahy jsou prirozena ne moc velka cisla. PDF
Mikkel Thorup: Floats, Integers, and Single Source Shortest Paths
Vylepsuje predchozi i na floaty, vyuziva ho jako podproceduru. PDF
Uriel Feige: On optimal strategies for a hat game on graphs
Hra s klobouky, v niz kazdy hrac sedi ve vrcholu grafu a vidi klobouky sousedu. Vsichni vyhraji, pokud aspon jeden tipne spravne a nikdo netipne spatne. Ukazuji se nejlepsi strategie pro bipartitni grafy a rovinne grafy s trojuhelnikem. PDF
Wesley Pegden: A finite goal set in the plane which is not a Winner
Je dana konecna mnozina bodu v rovine a hraci si stridave berou body roviny. Vyhrava ten ktery prvni ziska kopii zadane mnoziny. Zde mnozina o peti prvcich tak, ze druhy hrac muze vzdy vyhrat. PDF
E.R. van Dam, M.A. Fiol: A short proof of the odd-girth theorem
Novy dukaz, ze graf s d+1 vlastnimi cisly a lichym obvodem 2d+1 je vzdalenostne regularni (pocet sousedu u ve vzdalenosti j od v je stejny pro vsechny u a v ve vzdalenosti i). Bude asi tezke rict nejak smysluplne bez referenci. PDF
Jozsef Balogh, Andras Pluhar: The positive minimum degree game on sparse graphs
Maker a Breaker spolu hraji hru: Stridave si vybiraji hrany grafu a Maker vyhraje, pokud hrany ktere si vybral tvori graf s urcitym minimalnim stupnem. V clanku se vylepsuje mez na to, kolik musel mit puvodni graf hran, aby mohl Maker vyhrat. Jednoducha aplikace metody vybijeni (discharging). PDF
Sam Ganzfried: Computing Strong Game-Theoretic Strategies in Jotto
Hra kdy si kazdy hrac mysli tajne slovo a klade druhemu otazky ve forme slova. Odpovedi je pocet pismenek ktera jsou v obou slovech. Resi se jak pocitat strategie pocitacem. PDF
Andras Gyarfas, Gabor N. Sarkozy: Monochromatic path and cycle partitions in hypergraphs
Rozdelovani hranove obarvenych uniformnich hypergrafu na jednobarevne cesty a cykly. Asi bude potreba nahlidnout do referenci a nastudovat nazvoslovi. PDF
S. Akbari, N. Ghareghani, G. B. Khosrovshahi, S. Zare: A note on zero-sum 5-flows in regular graphs
Tok s nulovym souctem je prirazeni nenulovych realnych cisel hranam tak, ze soucet u kazdeho vrcholu je 0. Ukazuje se, ze r-regularni graf (r >= 3, r != 5) ma takovy tok pouzivajic jen cisla {-5, ..., -1, 1, ..., 5}. Samotny dukaz ma asi pul stranky, bude potreba nastudovat reference. PDF
Richard Ehrenborg, Chris M. Skinner: The Blind Bartender's Problem
Na otocnem stole ctyri sklenice, se zavazanyma ocima muzete vzdy obratit nejake dve, ale nekdo mezi tim toci stolem. Lze dosahnout toho, ze vsechny stejne? Zobecneni pro vice sklenic a slozitejsi stoly. Asi docela slozite, mozna se da neco vybrat. PDF
Laurie Kirby And Jeff Paris: Accessible Independence Results For Peano Arithmetic
Zabijeni hydry. Tvrzeni prvniho radu nezavisle na Peanove aritmetice. Asi trochu obtížnější, je potřeba vědet něco z logiky. PDF
Matula, Shiloach, Tarjan: Two linear time algorithms for five-coloring a planar graph
Vi se, ze kazdy rovinny graf je 4 barevny. Zde se ukazuje, jak obarvit rovinny graf 5-i barvami v linearnim case. PDF
Mark K. Goldberg and Malik Magdon-Ismail: Embedding a Forest in a Graph
Kazdy les lze vlozit do kazdeho grafu s dostatkem vrcholu. PDF
Janusz Dybizbanski: Sequences containing no 3-term arithmetic progressions
Jaka je nejdelsi podposloupnost posloupnosti 1, ..., n, ktera neobsahuje aritmetickou podposloupnost delky 3? Odhad s pomoci pocitace pro n <= 122. Velmi kratke. PDF
Joshua Erde, Bruno Golenia, Sylvain Golenia: The closed knight tour problem in higher dimensions
Lze nalezt uzavreny tah konem navstevujici kazde policko ctyr nebo vice dimenzionalni sachovnice prave jednou? Jeden z delsich, ale o to zajimavejsich. PDF
Yang Jiao: On the Sprague-Grundy Values of the F-Wythoff Game
Odebirani sirek ze dvou hromadek - bud z jedne, nebo stejne z obou. Zde navic pri odebirani z obou potreba zachovat celou cast pomeru velikosti. Ukazuji se zajimave vlastnosti o cislech charakterizujicich pozice z nichz jeden ci druhy ma vyherni strategii. PDF
Tamas Matrai: Covering the Edges of a Graph by Three Odd Subgraphs
Kazdy graf se da (hranove) pokryt trojici svych podgrafu, v nichz vsechny stupne jsou liche. PDF
Fan Chung, Ron Graham, Jia Mao, and Andrew Yao: Oblivious and Adaptive Strategies for the Majority and Plurality Problems
Mame n micku obarvenych dvema nebo vice barvami. Kolik porovnani barev je potreba abychom zjistili, jestli je nekterych micku vic nez polovina, nebo kterych je nejvice? PDF
Nathan Linial, Jaikumar Radhakrishnan: Essential covers of the cube by hyperplanes
Kolik polynomu je potreba, abychom pokryli hyperkrychli jejich koreny? PS
David R. Karger, Philip N. Klein, Robert E. Tarjan: A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees PDF
Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook: Linear-Time Pointer-Machine Algorithms for Least Common Ancestors,
MST Verification, and Dominators
Sjednoceni disjunktnich mnozin, radix sort s pointery a jejich spolecne pouziti k reseni vyse uvedenych. PDF
Haim Kaplan, Matthew J. Katz, Gila Morgenstern, and Micha Sharir: Optimal cover of points by disks in a simple polygon
Mame mnohouhelnik a v nem nekolik bodu. Chceme body pokryt kruhy ktere budou zcela v mnohouhelniku. Skoro linearni algoritmus. PDF
Zamluvené články
M. Reza Khani, Mohammad R. Salavatipour: Improved Approximation Algorithms for the Min-max Tree Cover and Bounded Tree Cover Problems
Pokryvame vrcholy grafu podstromama grafu, bud mame dany pocet a snazime se minimalizovat nejvetsi, nebo mame danou maximalni velikost a snazime se minimalizovat pocet. Ukazuji se approximace. PDF
Zamluveno pro: Barbora Červenková
Elliot Anshelevich, Bugra Caskurlu, Ameya Hate: Strategic Multiway Cut and Multicut Games
Zkouma se hra, ve ktere se vrcholy grafy snazi odrezat od nejake casti grafu. Porovnavaji se equilibria s centralnimi rozhodnutimi a ukazuje se, ze pro nektere scenare mohou byt dokonce stejne dobra. Delsi. PDF
Zamluveno pro: Lukáš Prokop
Články, které už byly
Yang Liu, Songjian Lu, Jianer Chen, Sing-Hoi Sze: Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
Hledání 3-dimenzionálního párování pomocí kódování barev, ukazuje se jak ušetřit tím, že obarvím jen dvě ze tří množin. PDF
Představil: Jakub Puchýř
Carlos Gómez-Rodríguez: Finding the smallest binarization of a CFG is NP-hard
Ukazuje, ze prevest bezkontextovou gramatiku na gramatiku v Chomskeho normalnim tvaru, ktera by byla nejmensi je NP-tezke. PDF
Představil: Jan Strnad
Maria Paola Bianchi, Hans-Joachim Böckenhauer, Juraj Hromkovič, Lucia Keller: Online Coloring of Bipartite Graphs with and without Advice
Barvime bipartitini graf tak, ze nam chodi vrcholy jeden po druhem a je nutne rovnou rozhodnou o jejich barve. Zde se ukazuje, ze takto bude potreba az log n barev (pro nektere grafy). Jsou tam dalsi vysledky, ale mozna staci tohle. PDF
Představil: Ondřej Fiedler
Agelos Georgakopoulos, Peter Winkler: Two-color Babylon
Ve hře Babylon jsou dány žetony různých barev, na začátku v hromádkách výšky 1.
Dva hráči střídavě pokládají 2 hromádky na sebe, pokud tyto hromádky mají stejnou výšku
nebo vrchní žetony mají stejnou barvu.
Článek studuje, jak hra dopadne pro žetony dvou barev. PDF
Představil: Jakub Doubek
Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest, Mihai Patraşcu: Picture-Hanging Puzzles
Jak povesit obraz na k hrebiku pomoci jednoho (zauzlovaneho) provazu tak, aby spadl, kdykoliv vyndate nejakych k hrebiku. Zkouma se, zda staci polynomialne uzlu. Bohate ilustrovane. PDF
Představil: Josef Malík
Abbas Mehrabian, Dieter Mitschey, Pawel Pralat: On the Maximum Density of Graphs with Unique-Path Labellings
Ukazuje se horni a dolni mez na pocet hran v grafu, ktery se da ocislovat tak, ze z kazdeho vrcholu do kazdeho vede nejvyse jedna cesta se vzrustajicimi cisly. Kratsi. PDF
Představil: Adam Kučera
Mike Paterson, Uri Zwick: Overhang
Skladame cihlicky na sebe, jak daleko pres okraj stolu mohou viset? Zde konstrukce s presahem theta(n^{1/3}), drive se znalo jen theta(log n). PDF
Představil: Robin Obůrka
Fei Li: A comprehensive study of an online packet scheduling algorithm
Na router s omezeným bufferem přicházejí pakety různé ceny, u kterých je
deadline na zpracování. Router musí rozhodovat, který paket odeslat a který
pozdržet tak, aby se maximalizoval zisk z paketů.
Článek popisuje a analyzuje online algoritmus pro tuto úlohu. PDF
Představil: Roman Jelínek
Giovanni Viglietta: Gaming Is a Hard Job, but Someone Has to Do It!
Ukazuje se nekolik metavet o postacujicich podminkach pro videohru, aby byla NP-tezka, nebo PSPACE-tezka. Take se ukazuje, ze vetsina videoher z let 1980-1998 takovych je. PDF
Představil: Stanislav Zubal
Yoshiaki Yamaguchi, Kazunori Yamaguchi, Tetsuro Tanaka, and Tomoyuki Kaneko: Infinite Connect-Four Is Solved: Draw
Hra kdy hraci X a O hazi kameny do sloupecku a vyhrava ten kdo ma ctyri v rade (svisle, vodorovne nebo diagonalne). V clanku strategie pro nejake varinaty s nekonecne mnoha sloupci. Kdyz oba hraji optimalne, hra je nekonecna. PDF
Představil: Jan Cejhon