Can I read Maximizing Dominance in the Plane and its Applications on EtoBox?

Maximizing Dominance in the Plane and its Applications by Jongmin Choi; Sergio Cabello; Hee-Kap Ahn is a Computer Science article available to read on EtoBox.

What is Maximizing Dominance in the Plane and its Applications about?

Given a set P of n weighted points, a set Q of m points in the plane, and a positive integer k, we consider the optimization problem of finding a subset of Q with at most k points that dominates a subset of P with maximum total weight. A set Q ′ of points in the plane dominates a point p in the plane if some point q ∈ Q satisfies x(p) ⩽ x(q) and y(p) ⩽ y(q) . We present an efficient algorithm solving this problem in O(k(n + m) log m) time and O(n + m) space. Our result implies algorithms with better time bounds for related problems, including the disjoint union of cliques problem for interval graphs (equivalently, the hitting intervals problem) and the top-k representative skyline points problem in the plane.

Who reads Maximizing Dominance in the Plane and its Applications?

Author

Jongmin Choi; Sergio Cabello; Hee-Kap Ahn

Publisher

Springer Science and Business Media LLC

Published

2021

Language

EN

Field

Computer Science (Physical Sciences)