8 citations · 30 across the 29 of their papers we have counts for
23 papers · 1 filter
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…
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…
Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns
Parinya Chalermsook, Seth Pettie, Sorrachai Yingchareonthawornchai
We consider the problem of comparison-sorting an -permutation that avoids some -permutation . Chalermsook, Goswami, Kozma, Mehlhorn, and Saranurak prove that when …
Polynomial-time Approximation of Independent Set Parameterized by Treewidth
Parinya Chalermsook, Fedor Fomin, Thekla Hamm +3
We prove the following result about approximating the maximum independent set in a graph. Informally, we show that any approximation algorithm with a ``non-trivial'' approximation…
Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
Fateme Abbasi, Sandip Banerjee, Jarosław Byrka +6
We consider the well-studied Robust -Clustering problem, which generalizes the classic -Median, -Means, and -Center problems. Given a constant , the input…