8 citations · 30 across the 29 of their papers we have counts for
38 papers
Hardness and Approximation for Coloring Digraphs
Parinya Chalermsook, Harmender Gahlawat, Felix Klingelhoefer +2
The dichromatic number of a digraph is the minimum number such that can be partitioned into subsets, each inducing an acyclic digraph. The acyclic number…
Fine-Grained Complexity of Continuous Euclidean k-Center
Lotte Blank, Karl Bringmann, Parinya Chalermsook +4
In the (continuous) Euclidean -center problem, given points in and an integer , the goal is to find center points in that minimize the m…
A Freeable Matrix Characterization of Bipartite Graphs of Ferrers Dimension Three
Parinya Chalermsook, Ly Orgo, Minoo Zarsav
Ferrer dimension, along with the order dimension, is a standard dimensional concept for bipartite graphs. In this paper, we prove that a graph is of Ferrer dimension three (equival…
On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers
Parinya Chalermsook, Ly Orgo, Minoo Zarsav
This paper considers the \textit{Zarankiewicz problem} in graphs with low-dimensional geometric representation (i.e., low Ferrers dimension). Our first result reveals a separation…
Shortcuts and Transitive-Closure Spanners Approximation
Parinya Chalermsook, Yonggang Jiang, Sagnik Mukhopadhyay +1
We study polynomial-time approximation algorithms for two closely-related problems, namely computing shortcuts and transitive-closure spanners (TC spanners). For a directed unweigh…
The Group Access Bounds for Binary Search Trees
Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak +2
The access lemma (Sleator and Tarjan, JACM 1985) is a property of binary search trees that implies interesting consequences such as static optimality, static finger, and working se…