1,720,981 research outputs found
Parameterized Algorithms for the Min-Power Symmetric Connectivity Problem
No full textV bakalářské práci představíme problém Min Power Symmetric connectivity (MinPSC), který je na obecných grafech NP-těžký. Problém MinPSC má uplatněni v sítích, kde pro daný uzel chceme zmenšit jeho spotřebu energii na co nejmenší úroveň a požadujeme přitom, aby každý uzel mohl komunikovat s ostatními. V této práci zkoumáme problém MinPSC ze pohledu dvou strukturálních parametru. A to z vrcholového pokrytí a sousedské různorodosti.In this bachelor thesis, we introduce Min Power Symmetric Connectivity (MinPSC) problem which is NP-complete. The application of the problem is in networks, where we want to reduce a consumption of energy as much as possible. And while it is required to have a connection between each node in the network. In this thesis, we examine the problem MinPSC from the point of view of two structural graph parameters. Vertex cover and neighbourhood diversity
Parameterized Algorithms for the Truncated Metric Dimension problem
Full text linkTato práce se zabývá FPT algoritmy řešící problém zkrácené metrické dimenze. Nejdříve představíme dva již známé algoritmy řešící problém metrické dimenze. Poté představíme dva jednoduché protipříklady algoritmu, jehož časová složitost je vázaná šířkou modulu, čímž ukážeme že nepracuje korektně. Dále navrhneme možnou úpravu, jež by mohla řešit popsané problémy s výpočtem. Algoritmus je dále implementován a testován. Ukážeme také proč algoritmus, jehož časová složitost je vázaná délkou stromu a největším stupněm vrcholu, není vhodný pro úpravu aby řešil problém zkrácené metrické dimenze.This thesis is about FPT algorithms that solve the Truncated Metric Dimension problem. First, two already known algorithms solving the metric dimension problem are described. Then we present two counterexamples to the algorithm bounded by modular width, showing the algorithm does not work correctly. Following that, we propose a possible solution, that might fix the described issues. The algorithm is then implemented and tested. It is also argued as to why the algorithm bounded by tree-length and max-degree is not suitable to solve the truncated metric dimension problem
Induced star partition of graphs with respect to structural parameters
Full text linkZabýváme se problémem Rozdělení na indukované hvězdy na neorientovaných grafech. Cílem je rozdělit graf na q množin S_1, ..., S_q tak, že každá množina S_i indukuje hvězdu (graf izomorfní grafu K_{1, r} pro nějaké r >= 0). Je známo, že pro každé pevné q >= 3 je tento problém NP-úplný. Existuje ale exaktní algoritmus, který dokáže rozdělit graf na q indukovaných hvězd v čase 3^n n^{O(1)} a použije polynomiálně mnoho paměti. Není nám známo, že by existoval exaktní parametrizovaný algoritmus pro tento problém. V této práci předvedeme následující výsledky: (1) Problém patří do třídy FPT pokud budeme parametrizovat vrcholovým pokrytím grafu a existuje exaktní algoritmus běžící v čase O(k^{2k+1} n^2), kde k je velikost minimálního vrcholového pokrytí grafu. (2) Problém patří do třídy FPT pokud budeme parametrizovat stromovou šířkou grafu a a existuje exaktní algoritmus běžící v čase O(tw(G)^{2tw(G)}* n), kde tw(G) je stromová šířka grafu. (3) Pro každé pevné q platí, že problém lze vyřešit v lineárním čase na grafech s omezenou klikovou šířkou. Také poskytujeme jednoduchou implementaci algoritmu parametrizovaného vrcholovým pokrytím grafu v jazyce C++ a vyhodnotili jsme výkonnost implementace.An induced star partition of an undirected graph G = (V, E) is a partition S_1, ..., S_q of V(G) such that each set S_i induces a star (graph isomorphic to K_{1, r} for some r >= 0. The Induced Star problem asks whether G admits an induced star partition of size q. This problem was proven to be NP-complete for each fixed q >=3 and has an exact 3^n n^{O(1)} time polynomial space algorithm. To the best of our knowledge, there are no known algorithms based on structural parameters for the problem. We present the following results: (1) The problem is FPT when parameterized by the vertex cover number of the graph and there is an exact O(k^{2k+1} n^2) time algorithm, where k is the vertex cover number of the input graph. (2) The problem is FPT when parameterized by the treewidth of the graph and there is an exact O(tw(G)^{2tw(G)} * n) time algorithm, where tw(G) is the treewidth of the input graph. (3) For a fixed q, the problem can be solved linear time on graphs with bounded cliquewidth. We also provide a simple implementation of our algorithm parameterized by the vertex cover number in C++ and evaluate its performance
Binary paint shop problem
No full textBinární paint shop je následující optimalizační úloha: Na barvicí linku vjíždí řa- da aut. Od každého typu auta jsou někde v řadě právě dvě auta a jedno z nich bychom rádi nabarvili červeně a druhé modře. Měnit barvu, kterou aktuálně bar- víme, je drahá operace, proto bychom rádi pro danou posloupnost aut provedli co nejméně změn. Vstupem úlohy jsou typy aut v posloupnosti a výstupem je jejich obarvení. Je známé, že úloha je NP-těžká a za určitých předpokladů dokon- ce neaproximovatelná, proto je na místě zkoumat řešení, co se chovají dobře na náhodném vstupu. V této práci je představen algoritmus založený na semidefinit- ním programování, který dle provedených měření pro náhodné vstupy dosahuje výsledků okolo 0.34-násobku počtu typů aut. O algoritmu jsme dokázali, že pro každý vstup vrátí ve střední hodnotě řešení nejhůře o 0.212-násobek počtu typů aut horší než optimum. 1The Binary Paint Shop represents an optimization problem: A line of cars enters a paint shop. There are exactly two cars of each type somewhere in the line. The aim is to color one of these two cars red and the other blue. It is expensive to switch the current color in the paint shop so for a given sequence of cars we would like to minimize the number of color changes. Input of the task are types of cars in the line and output is the coloring of theses cars. This task is known to be NP-hard, and under specific conditions, it defies polynomial time approximations. Therefore, it is a good idea to find some algorithms which behave well on a randomly generated input. This thesis introduces an algorithm based on semidefinite programming. Experiments on random inputs show it reaches solutions near to 0.34 times the number of car types. We proved that for each input this algorithm returns a solution with expected deviation from optimum of at most 0.212 times the number of car types. 1Computer Science Institute of Charles UniversityInformatický ústav Univerzity KarlovyMatematicko-fyzikální fakultaFaculty of Mathematics and Physic
Target Set Selection in Sparse and Geometric Networks
Full text linkV této práci se zabýváme následujícím modelem šíření názoru v sociální síti. Na začátku někteří jedinci přijmou jistý názor (například tak, že jsou uplaceni). Poté se názor v síti šíří v diskrétním smyslu podle následujících pravidel. Jedinec, který ještě tento názor nemá, jej přijme, pokud dostatečné množství jeho přímých sousedů už názor má. Úkolem pak je ovlivnit malé množství jedinců tak, aby názor zaplavil celou síť. Tento model odpovídá notoricky těžkému problému Target Set Selection. V této práci řešíme tento problém v geometricky motivovaných grafových třídách, konkrétně ve třídě unit disk grafů. Ukazujeme, že i pro tuto třídu je problém Target Set Selection NP-těžký i když má vstupní graf maximální stupeň 4 a~hodnota prahové funkce je nanejvýš 2. Také ukazujeme NP-těžkost v případě, kdy je prahová funkce nastavena na majoritu. Po cestě ukazujeme podobné výsledky pro související třídy grafů jako jsou disk contact grafy nebo mřížkové grafy.We study the following model of opinion spread in a social network. In the beginning, some individuals in the network adopt a concrete opinion (for example, they are bribed to adopt it). Next, in discrete rounds, the opinion spreads throughout the network in the following way. An individual that has not yet adopted the opinion, adopts it if a~sufficient number of its direct neighbors possess the opinion. The task is to initially influence a~small number of individuals such that the opinion floods the entire network. This model corresponds to a~notorious hard problem called Target Set Selection. In this work, we address geometric graphs, in particular, unit disk graphs. We show that even in this class Target Set Selection remains NP-hard, even if maximum degree of the underlying graph is 4 and thresholds are at most 2. We also show NP-hardness of Target Set Selection in the majority and unanimous threshold settings. En route, we show similar hardness results for related classes of graphs such as disk contact or grid graphs
Translation of MSOL formulas to finite automatons
No full textPoužití formální logiky pro verifikaci praktických řešení je dobře prozkoumaná metoda, využívaná mnoha různými obory od hardwarové verifikace až po syntézu kontrolerů. MONA je nástroj, který dostane na vstupu popis teorie a~jehož výstup je automat, který lze použít nejenom pro verifikaci, ale i~pro nalezení řešení. Je to starý nástroj, jehož kód je težké pochopit a ještě těžší modifikovat. Tato práce analyzuje, znovuvytváří a rozšiřuje schopnosti MONY.Using formal logic to verify practical solutions is a well-known method used by a wide variety of fields, ranging from hardware verification to controller synthesis. MONA is a tool that takes in a theory and outputs an automaton that can be used not only to verify, but also find solutions. It is an old tool, whose code is hard to comprehend and harder to modify. This thesis analyzes, recreates and expands MONA's capabilities
Binary paint shop problem
No full textThe Binary Paint Shop represents an optimization problem: A line of cars enters a paint shop. There are exactly two cars of each type somewhere in the line. The aim is to color one of these two cars red and the other blue. It is expensive to switch the current color in the paint shop so for a given sequence of cars we would like to minimize the number of color changes. Input of the task are types of cars in the line and output is the coloring of theses cars. This task is known to be NP-hard, and under specific conditions, it defies polynomial time approximations. Therefore, it is a good idea to find some algorithms which behave well on a randomly generated input. This thesis introduces an algorithm based on semidefinite programming. Experiments on random inputs show it reaches solutions near to 0.34 times the number of car types. We proved that for each input this algorithm returns a solution with expected deviation from optimum of at most 0.212 times the number of car types.
Computational Complexity of Maximum Betweenness Centrality: A Multivariate Analysis
Full text linkProblém Maximum Betweenness Centrality spočívá ve výběru skupiny úzlů uživateli zadané velikosti ze sociální sítě tak, abychom maximalizovali pravděpodobnost zachycení komunikace probíhající po nejkratších cestách v rámci sítě. Tento problém je významný pro výzkum sítí modelujících komunikace. Byť Maximum Betweenness Centrality je poměrně probádáný v kontextu klasické složitosti, jeho parametrizováná složitost představovala dosavaď nezdupanou půdu. Tento nedostatek doplníme multivarietní analýzou. Ukázujeme, že Maximum Betweenness Centrality je W[1]-těžký parametrizován velikostí skupiny. Tento výsledek doplňujeme dolní mezí f(b) * n^o(b) pro algoritmy pro Maximum Betweenness Centrality parametrizován velikostí skupiny b, za předpokladu, že platí ETH. Oproti tomu ukazujeme že Maximum Betweenness Centrality je v FPT když je parametrizován buďto parametrem vertex cover number, distance to clique a velikostí skupiny, nebo twin cover number a velikostí skupiny.The Maximum Betweenness Centrality problem consists in picking a group of b nodes from a social network so that it has the greatest likelihood of detecting communication, assuming that nodes communicate only along shortest paths, chosen uniformly at random. Finding such groups is relevant for the study of communication in complex networks. Although this problem has been studied within the framework of classical complexity, its parameterized complexity has remained an open question. We close this gap by studying Maximum Betweenness Centrality from a parameterized perspective. We show that Maximum Betweenness Centrality is W[1]-hard when parameterized by the budget b, and complement this result with a lower bound of f(b) * n^o(b) for any algorithm for Maximum Betweenness Centrality parameterized by the budget b, under ETH. On a positive tone, we show that Maximum Betweenness Centrality is in FPT when parameterized by the vertex cover number, by the distance to clique and the budget, or by the twin cover number and the budget
Parameterized Algorithms for the Truncated Metric Dimension problem
Full text linkTato práce se zabývá FPT algoritmy řešící problém Zkrácené Metrické Dimenze. Představíme dva již známé algoritmy řešící problém Metrické Dimenze. Pro algoritmus parametrizovaný šířkou modulu ukážeme jeho jednoduchou modifikaci tak, aby řešil problém Zkrácené Metrické Dimenze. Pro algoritmus parametrizovaný maximálním počtem listů vysvětlíme důvod, který nám zabránil jeho úpravám. Poté nastíníme implementaci algoritmů parametrizovaných šířkou modulu a ukážeme vybrané výkonnostní metriky.This thesis is directed at FPT algorithms that solve the Truncated Metric Dimension problem. Two already known algorithms solving the Metric Dimension problem are described. For the algorithm bounded by modular-width we present a simple modification for it to solve the Truncated Metric Dimension problem. As for the algorithm bounded by max leaf number, we describe the reason that prevented us from modifying the algorithm. Following that, we explain how we implemented the algorithms bounded by modular-width and show selected performance metrics
- …
