215 citations · 689 across the 60 of their papers we have counts for
5 papers · 1 filter
Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More
Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
Graph product is a fundamental tool with rich applications in both graph theory and theoretical computer science. It is usually studied in the form where and are g…
Dense Subgraphs on Dynamic Networks
Atish Das Sarma, Ashwin Lall, Danupon Nanongkai +1
In distributed networks, it is often useful for the nodes to be aware of dense subgraphs, e.g., such a dense subgraph could reveal dense subtructures in otherwise sparse graphs (e.…
Can Quantum Communication Speed Up Distributed Computation?
Michael Elkin, Hartmut Klauck, Danupon Nanongkai +1
The focus of this paper is on {\em quantum distributed} computation, where we investigate whether quantum communication can help in {\em speeding up} distributed network algorithms…
Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-partite graphs
Parinya Chalermsook, Shiva Kintali, Richard Lipton +1
Consider the following problem. A seller has infinite copies of products represented by nodes in a graph. There are consumers, each has a budget and wants to buy two produc…
Geometric Pricing: How Low Dimensionality Helps in Approximability
Parinya Chalermsook, Khaled Elbassioni, Danupon Nanongkai +1
Consider the following toy problem. There are rectangles and points on the plane. Each rectangle is a consumer with budget , who is interested in purchasing the ch…