Výsledky vyhledávání - "Theory of computation �� Fixed parameter tractability"

Sur la largeur des décompositions JSJ compliquées

Autor: Huszár, Kristóf, Spreer, Jonathan

Publikováno v: Leibniz International Proceedings in Informatics (LIPIcs)
39th International Symposium on Computational Geometry (SoCG 2023)
39th International Symposium on Computational Geometry (SoCG 2023), Jun 2023, Dallas, United States. pp.42:1--42:18, ⟨10.4230/LIPIcs.SoCG.2023.42⟩
Kristóf Huszár

Motivated by the algorithmic study of 3-dimensional manifolds, we explore the structural relationship between the JSJ decomposition of a given 3-manifold and its triangulations. Building on work of Bachman, Derby-Talbot and Sedgwick, we show that a "

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4ede02e45b3f15e058c198cd457ee474
https://hal.science/hal-04055617

Zobrazit plný text záznamu

Diverse collections in matroids and graphs

Autor: Fomin, Fedor V., Golovach, Petr A., Panolan, Fahad, Philip, Geevarghese, Saurabh, Saket

Publikováno v: Leibniz International Proceedings in Informatics

We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems, two from the theory of matroids and the third from graph theory. The input to the Weighted Diverse Bases problem consists of

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::02b9f5af3742101537b9a5687586e1fc
https://doi.org/10.1007/s10107-023-01959-z

Zobrazit plný text záznamu

A Polynomial Kernel for Funnel Arc Deletion Set

Autor: Garlet Milani, Marcelo

Publikováno v: Algorithmica. 84:2358-2378

In Directed Feeback Arc Set (DFAS) we search for a set of at most $k$ arcs which intersect every cycle in the input digraph. It is a well-known open problem in parameterized complexity to decide if DFAS admits a kernel of polynomial size. We consider

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::973a043bfe623d35edcfd4bd4f144f1e
https://doi.org/10.1007/s00453-022-00960-w

Zobrazit plný text záznamu

Twin-width VIII: delineation and win-wins

Autor: Bonnet, Édouard, Chakraborty, Dibyayan, Kim, Eun Jung, Köhler, Noleen, Lopes, Raul, Thomassé, Stéphan

Publikováno v: The International Symposium on Parameterized and Exact Computation (IPEC)
The International Symposium on Parameterized and Exact Computation (IPEC), Sep 2022, Potsdam, Germany

We introduce the notion of delineation. A graph class C is said delineated by twin-width (or simply, delineated) if for every hereditary closure D of a subclass of C, it holds that D has bounded twin-width if and only if D is monadically dependent. A

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0d899c4cb1fbd0a84ca990582c8d44d1
https://hal.science/hal-03956502

Zobrazit plný text záznamu

Galactic Token Sliding

Autor: Bartier, Valentin, Bousquet, Nicolas, Mouawad, Amer E.

Publikováno v: European Symposium on Algorithms
European Symposium on Algorithms, Sep 2022, Potsdam, Germany. ⟨10.4230/LIPIcs.ESA.2022.15⟩

Given a graph G and two independent sets I_s and I_t of size k, the Independent Set Reconfiguration problem asks whether there exists a sequence of independent sets (each of size k) I_s = I₀, I₁, I₂, …, I_𝓁 = I_t such that each independent

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::32cb482b0dcc4379c62ba1c24b6d4c19
https://hal.science/hal-03829754

Zobrazit plný text záznamu

Domination and cut problems on chordal graphs with bounded leafage

Autor: Galby, Esther, Marx, Dániel, Schepper, Philipp, Sharma, Roohani, Tale, Prafullkumar

Publikováno v: International Symposium on Parameterized and Exact Computation (IPEC 2022)
17th International Symposium on Parameterized and Exact Computation
Leibniz International Proceedings in Informatics

The leafage of a chordal graph G is the minimum integer l such that G can be realized as an intersection graph of subtrees of a tree with l leaves. We consider structural parameterization by the leafage of classical domination and cut problems on cho

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6548a3278e56620ad7210223aa7aee07
https://hdl.handle.net/11420/14451

Zobrazit plný text záznamu

On the parameterized complexity of symmetric directed multicut

Autor: Eiben, Eduard, Rambaud, Clément, Wahlström, Magnus

We study the problem Symmetric Directed Multicut from a parameterized complexity perspective. In this problem, the input is a digraph $D$, a set of cut requests $C=\{(s_1,t_1),\ldots,(s_\ell,t_\ell)\}$ and an integer $k$, and the task is to find a se

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::20f79708995043cea9f89fe594d47fdb
http://arxiv.org/abs/2208.09017

Zobrazit plný text záznamu

Deciding twin-width at most 4 is NP-complete

Autor: Bergé, Pierre, Bonnet, Édouard, Déprés, Hugues

Publikováno v: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
49th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2022)
49th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2022), Jul 2022, Paris, France. ⟨10.4230/LIPIcs.ICALP.2022.18⟩

We show that determining if an $n$-vertex graph has twin-width at most 4 is NP-complete, and requires time $2^{\Omega(n/\log n)}$ unless the Exponential-Time Hypothesis fails. Along the way, we give an elementary proof that $n$-vertex graphs subdivid

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::511eff5f965748618df6eb45c0a351d0
https://hal.science/hal-03750997

Zobrazit plný text záznamu

On Polynomial Kernels for Traveling Salesperson Problem and its Generalizations

Autor: Blažej, Václav, Choudhary, Pratibha, Knop, Dušan, Schierreich, Šimon, Suchý, Ondřej, Valla, Tomáš

For many problems, the important instances from practice possess certain structure that one should reflect in the design of specific algorithms. As data reduction is an important and inextricable part of today’s computation, we employ one of the mo

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::292372ca74bde02958d9f28f802d2b69
http://arxiv.org/abs/2207.01109

Zobrazit plný text záznamu

Search-Space Reduction via Essential Vertices

Autor: Bumpus, Benjamin Merlin, Jansen, Bart M. P., de Kroon, Jari J. H.

We investigate preprocessing for vertex-subset problems on graphs. While the notion of kernelization, originating in parameterized complexity theory, is a formalization of provably effective preprocessing aimed at reducing the total instance size, ou

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::175348f667a6432a945157f63bd854f5
http://arxiv.org/abs/2207.00386

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání