A Polynomial Kernel for 3-Leaf Power Deletion

Autor: Ahn, Jungho, Eiben, Eduard, Kwon, O-joung, Oum, Sang-il

Publikováno v: Algorithmica.

For a non-negative integer $\ell$, a graph $G$ is an $\ell$-leaf power of a tree $T$ if $V(G)$ is equal to the set of leaves of $T$, and distinct vertices $v$ and $w$ of $G$ are adjacent if and only if the distance between $v$ and $w$ in $T$ is at mo

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ae85473080b4236e5623599927b6f62b
https://doi.org/10.1007/s00453-023-01129-9

Romeo and Juliet Meeting in Forest Like Regions

Autor: Misra, Neeldhara, Mulpuri, Manas, Tale, Prafullkumar, Viramgami, Gaurav

The game of rendezvous with adversaries is a game on a graph played by two players: Facilitator and Divider. Facilitator has two agents and Divider has a team of $k \ge 1$ agents. While the initial positions of Facilitator's agents are fixed, Divider

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0becd9de30d185221e4391b59c2d913c
https://doi.org/10.21203/rs.3.rs-2850290/v1

Approximate Selection with Unreliable Comparisons in Optimal Expected Time

Autor: Huang, Shengyu, Liu, Chih-Hung, Rutschmann, Daniel

Publikováno v: Huang, S, Liu, C H & Rutschmann, D 2023, Approximate Selection with Unreliable Comparisons in Optimal Expected Time . in Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science : STACS 2023 ., 37, Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 254, 40th International Symposium on Theoretical Aspects of Computer Science, Hamburg, Germany, 07/03/2023 . https://doi.org/10.4230/LIPIcs.STACS.2023.37

Given n elements, an integer k ≤ n/2 and a parameter ε ≥ 1/n, we study the problem of selecting an element with rank in (k-nε, k+nε] using unreliable comparisons where the outcome of each comparison is incorrect independently with a constant e

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::90b6707132394904a188a5df6a6985b4

Approximation Algorithms for the Longest Run Subsequence Problem

Autor: Asahiro, Yuichi, Eto, Hiroshi, Gong, Mingyang, Jansson, Jesper, Lin, Guohui, Miyano, Eiji, Ono, Hirotaka, Tanaka, Shunichi

We study the approximability of the Longest Run Subsequence problem (LRS for short). For a string S = s_1 ⋯ s_n over an alphabet Σ, a run of a symbol σ ∈ Σ in S is a maximal substring of consecutive occurrences of σ. A run subsequence S' of S

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::935cb0128fda7f676960d6c7cf938e45

Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width

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

For any $\varepsilon > 0$, we give a polynomial-time $n^\varepsilon$-approximation algorithm for Max Independent Set in graphs of bounded twin-width given with an $O(1)$-sequence. This result is derived from the following time-approximation trade-off

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::19d2cf524517c86a78c3c0641a0b650d