Дисертації з теми "Parameterized complexity algorithms"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся з топ-29 дисертацій для дослідження на тему "Parameterized complexity algorithms".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Переглядайте дисертації для різних дисциплін та оформлюйте правильно вашу бібліографію.
Xia, Ge. "Parameterized algorithms and computational lower bounds: a structural approach." Texas A&M University, 2005. http://hdl.handle.net/1969.1/4322.
Kim, Eun Jung. "Parameterized algorithms on digraph and constraint satisfaction problems." Thesis, Royal Holloway, University of London, 2010. http://repository.royalholloway.ac.uk/items/4e3a1971-6e98-97a9-8e4f-9e1fdc76066a/9/.
Enciso, Rosa. "Alliances in Graphs: Parameterized Algorithms and on Partitioning Series-Parallel Graphs." Doctoral diss., University of Central Florida, 2009. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/2479.
Ph.D.
School of Electrical Engineering and Computer Science
Engineering and Computer Science
Computer Science PhD
Dinh, Hiep. "Exploring Algorithms for Branch Decompositions of Planar Graphs." Ohio University / OhioLINK, 2008. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1222984625.
Zhang, Fenghui. "Effective algorithms and protocols for wireless networking: a topological approach." Diss., Texas A&M University, 2008. http://hdl.handle.net/1969.1/86012.
Chan, Hubert. "A Parameterized Algorithm for Upward Planarity Testing of Biconnected Graphs." Thesis, University of Waterloo, 2003. http://hdl.handle.net/10012/1090.
Cadena, Jose Eduardo. "Finding Interesting Subgraphs with Guarantees." Diss., Virginia Tech, 2018. http://hdl.handle.net/10919/81960.
Ph. D.
Sau, Ignasi. "Optimization in Graphs under Degree Constraints. Application to Telecommunication Networks." Phd thesis, Université de Nice Sophia-Antipolis, 2009. http://tel.archives-ouvertes.fr/tel-00429092.
Daligault, Jean. "Techniques combinatoires pour les algorithmes paramétrés et les noyaux, avec applications aux problèmes de multicoupe." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2011. http://tel.archives-ouvertes.fr/tel-00804206.
Chopin, Morgan. "Problèmes d'optimisation avec propagation dans les graphes : complexité paramétrée et approximation." Phd thesis, Université Paris Dauphine - Paris IX, 2013. http://tel.archives-ouvertes.fr/tel-00933769.
Parsa, Mahdi. "Parameterized Complexity Applied in Algorithmic Game Theory." Thesis, Griffith University, 2011. http://hdl.handle.net/10072/367212.
Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Institute for Integrated and Intelligent Systems
Science, Environment, Engineering and Technology
Full Text
Perez, Anthony. "Algorithmes de noyau pour des problèmes d'édition de graphes et autres structures." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2011. http://tel.archives-ouvertes.fr/tel-00660089.
Chapelle, Mathieu. "Décompositions de graphes : quelques limites et obstructions." Phd thesis, Université d'Orléans, 2011. http://tel.archives-ouvertes.fr/tel-00659666.
Khosravian, Ghadikolaei Mehdi. "Extension of NP Optimization Problems." Thesis, Paris Sciences et Lettres (ComUE), 2019. http://www.theses.fr/2019PSLED064.
The problem of determining the quality of a partial solution occurs in almost every algorithmic approach that gradually computes a global solution. Pruning search trees, proving approximation guarantees, or the efficiency of enumeration strategies usually require a suitable way to decide if a given partial solution is a reasonable candidate to pursue for extension to a global one, of assured quality. In this thesis, we study a special type of optimization problems, called extension problems for a large number of optimization problems on graphs. Possibly contradicting intuition, these problems tend to be NP-hard, even for problems where the underlying optimization problem can be solved in polynomial time. We present many positive/negative hardness and approximation results for different input scenarios. Moreover, the parameterized complexity of extension problems with respect to size of partial solutions, as well as the optimality of some exact algorithms under the Exponential-Time Hypothesis (ETH) are studied
Bonnet, Edouard. "Résultats Positifs et Négatifs en Approximation et Complexité Paramétrée." Thesis, Paris 9, 2014. http://www.theses.fr/2014PA090040/document.
Several real-Life problems are NP-Hard and cannot be solved in polynomial time.The two main options to overcome this issue are: approximation and parameterized complexity. In this thesis, we present a new technique called greediness-For-Parameterization and we use it to improve the parameterized complexity of many problems. We also use this notion to obtain parameterized algorithms for some problems in bipartite graphs. Aiming at establishing negative results on the approximability in subexponential time and in parameterized time, we introduce new methods of sparsification that preserves approximation. We combine those "sparsifiers" with known or new reductions to achieve our goal. Finally, we present some hardness results of games such as Bridge and Havannah
Yacoub, Taher. "Développement et implémentation d'une approche par fragments pour le design d'ARNs modifiés simple brin avec évaluation sur des protéines de liaison à l'ARN et un modèle d'étude la Bêta-Sécrétase 1." Electronic Thesis or Diss., université Paris-Saclay, 2024. http://www.theses.fr/2024UPASL002.
New therapeutic strategies have emerged using aptamers that are high-affinity ligands generated using a procedure called SELEX. Nevertheless, their use are limited due to the lack of selectivity and off-target effects frequently observed as in all RNA-based therapeutic strategies. In order to increase their specificity and selectivity, a class of chemically modified aptamers has been designed in-situ by SELEX (“SOMAmers”). But, various limitations remain due to technical constraints in SELEX, in particular the number and the type of chemical modifications that can be used. We propose a new fragment-based strategy to design in-silico modified aptamers that will overcome some of these limitations, based on the knowledge of 3D structure and the color-coding technique introduced by Alon, Yuster and Zwick. This approach is based on the modeling of pose connectivity in the form of a graph, enabling the implementation of an efficient combinatorial algorithm using dynamic programming. It is used for the “Docking” from a given fragment distribution, the “Design” and the equilibrium statistics for learning features between fragments and the 3D protein, and has been the subject of a proof of concept on 7 ssRNA/protein complexes.To test this new approach on a real therapeutic case study, an analysis has been carried out on the Beta-Secretase 1 (BACE1), an enzyme involved in Alzheimer's disease, and the Beta-Secretase 2 (a homologous protein to BACE1) to determine the key features of specificity and to select the modified nucleotides that bind sites and subsites of BACE1. These results can provide a basis for the design of selective ssRNA and for the evaluation of the Color-Coding based methodology
Bergé, Pierre. "Algorithmes pour voyager sur un graphe contenant des blocages." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLS480.
We study NP-hard problems on graphs with blockages seen as models of networks which are exposed to risk of failures.We treat cut problems via the parameterized complexity framework. The cutset size p is taken as a parameter. Given a set of sources {s1,...,sk} and a target $t, we propose an algorithm which builds a small edge cut of size p separating at least r sources from t. This NP-complete problem is called Partial One-Target Cut. It belongs to the family of multiterminal cut problems. Our algorithm is fixed-parameter tractable (FPT) as its execution takes $2^{O(p^2)}n^{O(1)}$. We prove that the vertex version of this problem, which imposes cuts to contain vertices instead of edges, is W[1]-hard. Then, we design an FPT algorithm which counts the minimum vertex (S,T)-cuts of an undirected graph in time $2^{O(plog p)}n^{O(1)}$.We provide numerous results on the competitive ratio of both deterministic and randomized strategies for the Canadian Traveller Problem. The optimal ratio obtained for the deterministic strategies on general graphs is 2k+1, where k is a given upper bound on the number of blockages. We show that randomized strategies which do not use memory cannot improve the bound 2k+1. In addition, we discuss the tightness of lower bounds on the competitiveness of randomized strategies. The distance competitive ratio for a group of travellers possibly equipped with telecommunication devices is studied. Eventually, a strategy dedicated to equal-weight chordal graphs is proposed while another one is built for graphs with small maximum (s,t)-cuts. Both strategies outperform the ratio 2k+1
Watrigant, Rémi. "Approximation et complexité paramétrée de problèmes d’optimisation dans les graphes : partitions et sous-graphes." Thesis, Montpellier 2, 2014. http://www.theses.fr/2014MON20100/document.
The theory of NP-completeness tells us that for many optimization problems, there is no hope for finding an efficient algorithm computing an optimal solution. Based on this, two classical approaches have been developped to deal with these problems. The first one, called polynomial- time approximation, consists in designing efficient algorithms computing a solution that is close to an optimal one. The second one, called param- eterized complexity, consists in designing exact algorithms which com- binatorial explosion is captured by a carefully chosen parameter of the instance. The goal of this thesis is twofold. First, we study and apply classical methods from these two domains in order to obtain positive and negative results for two optimization problems in graphs: a partitioning problem called Sparsest k-Compaction, and a cardinality constraint subgraph problem called Sparsest k-Subgraph. Then, we present how the different methods from these two domains have been combined in recent years in a concept called parameterized approximation. In particular, we study the links between approximation and kernelization algorithms
Watel, Dimitri. "Approximation de l'arborescence de Steiner." Thesis, Versailles-St Quentin en Yvelines, 2014. http://www.theses.fr/2014VERS0025/document.
The directed Steiner tree problem (DST) asks, considering a directed weighted graph, a node r called root and a set of nodes X called terminals, for a minimum cost directed tree rooted in r spanning X. DST is an NP-complete problem. We are interested in the search for polynomial approximations for DST. Unless P = NP, DST can not be approximated neither within a constant ratio nor a logarithmic ratio with respected to k, where k is the number of terminals. The smallest known approximation ratio is O(kԑ)$ where ԑ is a positive real.In the first part, we provide three new approximation algorithms : a practical greedy algorithm merging two of the main approximation techniques for DST, an algorithm for the case where the graph is layered and where the distance between the terminals and the root is high, and an exponential approximation algorithm combining an approximation algorithm and an exact algorithm, parameterized with the number of terminals the exact algorithm must cover.In the last part we study DST with two branching constraints. With this technique, we are able to reduce the number of feasible solutions, and possibly facilitate the search for an optimal solution of the constraint problem. We study how it is possible to build such a solution in polynomial time and if this solution is a good approximation of an optimal solution of the non-constraint problem
Meeks, Kitty M. F. T. "Graph colourings and games." Thesis, University of Oxford, 2012. http://ora.ox.ac.uk/objects/uuid:a805a379-f891-4250-9a7d-df109f9f52e2.
Garnero, Valentin. "(Méta)-noyaux constructifs et linéaires dans les graphes peu denses." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT328/document.
In the fields of Algorithmic and Complexity, a large area of research is based on the assumption that P ≠ NP(Polynomial time and Non deterministic Polynomial time), which means that there are problems for which a solution can be verified but not constructed in polynomial time. Many natural problems are not in P, which means, that they have no efficient algorithm. In order to tackle such problems, many different branches of Algorithmic have been developed. One of them is called Parametric Complexity. It consists in developing exact algorithms whose complexity is measured as a function of the size of the instance and of a parameter. Such a parameter allows a more precise analysis of the complexity. In this context, an algorithm will be considered to be efficient if it is fixed parameter tractable (fpt), that is, if it has a complexity which is exponential in the parameter and polynomial in the size of the instance. Problems that can be solved by such an algorithm form the FPT class.Kernelisation is a technical that produces fpt algorithms, among others. It can be viewed as a preprocessing of the instance, with a guarantee on the compression of the data. More formally, a kernelisation is a polynomial reduction from a problem to itself, with the additional constraint that the size of the kernel, the reduced instance, is bounded by a function of the parameter. In order to obtain an fpt algorithm, it is sufficient to solve the problem in the reduced instance, by brute-force for example (which has exponential complexity, in the parameter). Hence, the existence of a kernelisiation implies the existence of an fpt algorithm. It holds that the converse is true also. Nevertheless, the existence of an efficient fpt algorithm does not imply a small kernel, meaning a kernel with a linear or polynomial size. Under certain hypotheses, it can be proved that some problems can not have a kernel (that is, are not in FPT) and that some problems in FPT do not have a polynomial kernel.One of the main results in the field of Kernelisation is the construction of a linear kernel for the Dominating Set problem on planar graphs, by Alber, Fellows and Niedermeier.To begin with, the region decomposition method proposed by Alber, Fellows and Niedermeier has been reused many times to develop kernels for variants of Dominating Set on planar graphs. Nevertheless, this method had quite a few inaccuracies, which has invalidated the proofs. In the first part of our thesis, we present a more thorough version of this method and we illustrate it with two examples: Red Blue Dominating Set and Total Dominating Set.Next, the method has been generalised to larger classes of graphs (bounded genus, minor-free, topological-minor-free), and to larger families of problems. These meta-results prove the existence of a linear or polynomial kernel for all problems verifying some generic conditions, on a class of sparse graphs. As a price of generality, the proofs do not provide constructive algorithms and the bound on the size of the kernel is not explicit. In the second part of our thesis, we make a first step to constructive meta-results. We propose a framework to build linear kernels based on principles of dynamic programming and a meta-result of Bodlaender, Fomin, Lokshtanov, Penninkx, Saurabh and Thilikos
Sikora, Florian. "Aspects algorithmiques de la comparaison d'éléments biologiques." Phd thesis, Université Paris-Est, 2011. http://pastel.archives-ouvertes.fr/pastel-00667797.
Scott, Allan Edward Jolicoeur. "Classical and parameterized complexity of cliques and games." 2004. http://hdl.handle.net/1828/493.
Goyal, Prachi. "Parameterized Complexity of Maximum Edge Coloring in Graphs." Thesis, 2012. https://etd.iisc.ac.in/handle/2005/3255.
Goyal, Prachi. "Parameterized Complexity of Maximum Edge Coloring in Graphs." Thesis, 2012. http://hdl.handle.net/2005/3255.
Włodarczyk, Michał. "Approximation algorithms: new results for stochastic and parameterized problems." Doctoral thesis, 2019. https://depotuw.ceon.pl/handle/item/3435.
Niniejsza rozprawa doktorska oparta jest na 3 artykułach, które opublikowałem w trakcie studiów III stopnia. Zawierają one nowatorskie wyniki z dziedziny algorytmów aproksymacyjnych. Dwie prace dotyczą poddziedziny optymalizacji stochastycznej, zaś wyniki ostatniej pracy leżą w przecięciu teorii algorytmów aproksymacyjnych i złożoności parametryzowanej. Przedstawione wyniki zawierają m.in. analizę algorytmów dla problemów pokryciowych w obliczu niepewności danych. W tym modelu rozważamy problemy takie jak np. Set Cover, przy założeniu, że cześć danych wejściowych jest nieznana z góry, zaś algorytm ma dostęp do rozkładu prawdopodobieństwa opisującego dane. Celem jest zbudowanie takiej struktury danych, która pozwoli odtworzyć rozwiązanie, kiedy całość danych zostanie ujawniona. Innym zagadnieniem jest konstrukcja mechanizmów i aukcji, w których decyzję odnośnie każdego klienta/przedmiotu należy podjąć zanim poznamy stan pozostałych. Poszukujemy strategii maksymalizującej oczekiwany zysk mechanizmu w oparciu o rozkład prawdopodobieństwa modelujący stan klientów/przedmiotów. W ostatniej części skupiam się na problemach grafowych, w których celem jest usunięcie możliwie małego podzbioru wierzchołków, tak aby graf należał do zadanej klasy. W prezentowanej pracy udało się osiągnąć znaczącą poprawę współczynników aproksymacji lub czasu działania algorytmów dla szeregu problemów tego typu.
Pourhassan, Mojgan. "Parameterised complexity analysis of evolutionary algorithms for combinatorial optimization problems." Thesis, 2017. http://hdl.handle.net/2440/109799.
Thesis (Ph.D.) -- University of Adelaide, School of Computer Science, 2017.
Knop, Dušan. "Strukturální vlastnosti grafů a efektivní algoritmy: Problémy separující parametry." Doctoral thesis, 2017. http://www.nusl.cz/ntk/nusl-392435.
Scott, Allan Edward Jolicoeur. "On the parameterized complexity of finding short winning strategies in combinatorial games." Thesis, 2009. http://hdl.handle.net/1828/2676.