Zobrazeno 1 - 10
of 2 738
pro vyhledávání: '"kim eun jung"'
Given a graph $G$ and an integer $b$, Bandwidth asks whether there exists a bijection $\pi$ from $V(G)$ to $\{1, \ldots, |V(G)|\}$ such that $\max_{\{u, v \} \in E(G)} | \pi(u) - \pi(v) | \leq b$. This is a classical NP-complete problem, known to rem
Externí odkaz:
http://arxiv.org/abs/2309.17204
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, vol. 26:2, Discrete Algorithms (August 20, 2024) dmtcs:10810
A matroid $M$ is an ordered pair $(E,I)$, where $E$ is a finite set called the ground set and a collection $I\subset 2^{E}$ called the independent sets which satisfy the conditions: (i) $\emptyset \in I$, (ii) $I'\subset I \in I$ implies $I'\in I$, a
Externí odkaz:
http://arxiv.org/abs/2301.03221
Publikováno v:
SIAM Journal on Discrete Mathematics 38(1), 170-189, 2024
One of the first application of the recently introduced technique of \emph{flow-augmentation} [Kim et al., STOC 2022] is a fixed-parameter algorithm for the weighted version of \textsc{Directed Feedback Vertex Set}, a landmark problem in parameterize
Externí odkaz:
http://arxiv.org/abs/2208.14841
We study the parameterized problem of satisfying ``almost all'' constraints of a given formula $F$ over a fixed, finite Boolean constraint language $\Gamma$, with or without weights. More precisely, for each finite Boolean constraint language $\Gamma
Externí odkaz:
http://arxiv.org/abs/2207.07422
The recently introduced graph parameter tree-cut width plays a similar role with respect to immersions as the graph parameter treewidth plays with respect to minors. In this paper, we provide the first algorithmic applications of tree-cut width to ha
Externí odkaz:
http://arxiv.org/abs/2206.00752
Autor:
Bonnet, Édouard, Chakraborty, Dibyayan, Kim, Eun Jung, Köhler, Noleen, Lopes, Raul, Thomassé, Stéphan
We introduce the notion of delineation. A graph class $\mathcal C$ is said delineated if for every hereditary closure $\mathcal D$ of a subclass of $\mathcal C$, it holds that $\mathcal D$ has bounded twin-width if and only if $\mathcal D$ is monadic
Externí odkaz:
http://arxiv.org/abs/2204.00722
Autor:
Mahmud, Farabi, Kim, Sungkeun, Chawla, Harpreet Singh, Tsai, Chia-Che, Kim, Eun Jung, Muzahid, Abdullah
Publikováno v:
Annual Computer Security Applications Conference ACSAC 2023
For a distributed last-level cache (LLC) in a large multicore chip, the access time to one LLC bank can significantly differ from that to another due to the difference in physical distance. In this paper, we successfully demonstrated a new distance-b
Externí odkaz:
http://arxiv.org/abs/2112.10028
We show a flow-augmentation algorithm in directed graphs: There exists a randomized polynomial-time algorithm that, given a directed graph $G$, two vertices $s,t \in V(G)$, and an integer $k$, adds (randomly) to $G$ a number of arcs such that for eve
Externí odkaz:
http://arxiv.org/abs/2111.03450
A contraction sequence of a graph consists of iteratively merging two of its vertices until only one vertex remains. The recently introduced twin-width graph invariant is based on contraction sequences. More precisely, if one puts red edges between t
Externí odkaz:
http://arxiv.org/abs/2111.00282
Autor:
Bonamy, Marthe, Bonnet, Édouard, Bousquet, Nicolas, Charbit, Pierre, Giannopoulos, Panos, Kim, Eun Jung, Rzążewski, Paweł, Sikora, Florian, Thomassé, Stéphan
Publikováno v:
J. ACM 68(2): 9:1-9:38 (2021)
A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for \textsc{Maximum Clique} on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematic
Externí odkaz:
http://arxiv.org/abs/2110.15419