Selected Papers of the 32nd International Workshop on Combinatorial Algorithms, IWOCA 2021 [0.03%]
第32届组合算法国际研讨会（IWOCA 2021）精选论文
Paola Flocchini,Lucia Moura
Paola Flocchini
Alejandro Grez,Filip Mazowiecki,Michał Pilipczuk et al.
Alejandro Grez et al.
We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so through the lenses of parameterized dynamic data structures: we assu...
Special Issue Dedicated to the 16th International Symposium on Parameterized and Exact Computation [0.03%]
第十六届参数化和精确计算国际会议特刊
Petr A Golovach,Meirav Zehavi
Petr A Golovach
Selected Papers of the 31st International Workshop on Combinatorial Algorithms, IWOCA 2020 [0.03%]
第31届国际组合算法研讨会精选论文集（IWOTA 2020）
Leszek Gąsieniec,Ralf Klasing,Tomasz Radzik
Leszek Gąsieniec
Clemens Heuberger,Daniel Krenn,Gabriel F Lipnik
Clemens Heuberger
For an integer q ≥ 2 , a q-recursive sequence is defined by recurrence relations on subsequences of indices modulo some powers of q. In this article, q-recursive sequences are studied and the asymptotic behavior of their summatory fu...
On the Fine-grained Parameterized Complexity of Partial Scheduling to Minimize the Makespan [0.03%]
部分调度的精细参数复杂性以最小化工期
Jesper Nederlof,Céline M F Swennenhuis
Jesper Nederlof
We study a natural variant of scheduling that we call partial scheduling: in this variant an instance of a scheduling problem along with an integer k is given and one seeks an optimal schedule where not all, but only k jobs, have to be proc...
Łukasz Bożyk,Jan Derbisz,Tomasz Krawczyk et al.
Łukasz Bożyk et al.
A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines ℓ 1 and ℓ 2 , one on each. A bipartite permutation graph is a permutation graph which is bipartite. In this pape...
Fedor V Fomin,Petr A Golovach,William Lochet et al.
Fedor V Fomin et al.
We initiate the parameterized complexity study of minimum t-spanner problems on directed graphs. For a positive integer t, a multiplicative t-spanner of a (directed) graph G is a spanning subgraph H such that the distance between any two ve...
Vít Jelínek,Tereza Klimošová,Tomáš Masařík et al.
Vít Jelínek et al.
The 3-coloring of hereditary graph classes has been a deeply-researched problem in the last decade. A hereditary graph class is characterized by a (possibly infinite) list of minimal forbidden induced subgraphs H 1 , H 2 , … ; the g...
Dennis Komm,Rastislav Královič,Richard Královič et al.
Dennis Komm et al.
We study the relationship between the competitive ratio and the tail distribution of randomized online problems. To this end, we identify a broad class of online problems for which the existence of a randomized online algorithm with constan...