Titlebook: Algorithmsand Complexity; 12th International C Tiziana Calamoneri,Federico Corò Conference proceedings 2021 Springer Nature Switzerland AG

faction

Throughput Scheduling with Equal Additive Laxityin polynomial time. This contrasts the strong NP-hardness of the problem variant with arbitrary (and even equal multiplicative) laxity. Further, we give a fully polynomial-time approximation scheme for the weakly NP-hard weighted problem. Our single-machine algorithm can be used repeatedly to schedu

盖他为秘密

Fragile Complexity of Adaptive Algorithms . is the number of increasing runs in a sequence. Deterministically finding the median has fragile complexity . and .. Deterministic sorting has fragile complexity . but it has fragile complexity . regardless of the number of runs.

thalamus

FPT and Kernelization Algorithms for the Induced Tree Problem does not admit an . time algorithm. Afterwards, we use Courcelle’s Theorem to prove tractability under cliquewidth, which prompts our investigation into which parameterizations admit single exponential algorithms; we show that such algorithms exist for the unrelated parameterizations treewidth, dis

Brain-Waves

A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGsar if its underlying undirected graph is planar) directed graphs is unknown..   We resolve this gap by showing that . is W[1]-hard parameterized by the number . of terminal pairs, even when the input graph is a planar directed acyclic graph (DAG). This answers a question of Slivkins (ESA ’03, SIDMA

离开

Upper Dominating Set: Tight Algorithms for Pathwidth and Sub-exponential Approximationo .. We finally show that this time-approximation trade-off is tight, up to an arbitrarily small constant in the second exponent: under the randomized ETH, and for any ratio . and ., no algorithm can output an .-approximation in time .. Hence, we completely characterize the approximability of the pr

Isolate

On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineeringletions. Nevertheless, we develop several effective data reduction and pruning rules, resulting in a competitive solver, outperforming a standard CPLEX solver in most instances of an established biological test data set.

Ardent