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...
Dan Alistarh,Giorgi Nadiradze,Amirmojtaba Sabour
Dan Alistarh
We consider the following dynamic load-balancing process: given an underlying graph G with n nodes, in each step t ≥ 0 , a random edge is chosen, one unit of load is created, and placed at one of the endpoints. In the same step, assu...
Ioannis Caragiannis,Panagiotis Kanellopoulos,Alexandros A Voudouris
Ioannis Caragiannis
Social networks on the Internet have seen an enormous growth recently and play a crucial role in different aspects of today's life. They have facilitated information dissemination in ways that have been beneficial for their users but they a...