Zobrazeno 1 - 10
of 64
pro vyhledávání: '"Keil, J. Mark"'
The classical 3SUM conjecture states that the class of 3SUM-hard problems does not admit a truly subquadratic $O(n^{2-\delta})$-time algorithm, where $\delta >0$, in classical computing. The geometric 3SUM-hard problems have widely been studied in co
Externí odkaz:
http://arxiv.org/abs/2404.04535
Autor:
Keil, J. Mark, Mondal, Debajyoti
A disk graph is an intersection graph of disks in $\mathbb{R}^2$. Determining the computational complexity of finding a maximum clique in a disk graph is a long-standing open problem. In 1990, Clark, Colbourn, and Johnson gave a polynomial-time algor
Externí odkaz:
http://arxiv.org/abs/2404.03751
A disk graph is an intersection graph of disks in the Euclidean plane, where the disks correspond to the vertices of the graph and a pair of vertices are adjacent if and only if their corresponding disks intersect. The problem of determining the time
Externí odkaz:
http://arxiv.org/abs/2303.07645
Given a set $P$ of points in the plane, a point burning process is a discrete time process to burn all the points of $P$ where fires must be initiated at the given points. Specifically, the point burning process starts with a single burnt point from
Externí odkaz:
http://arxiv.org/abs/2209.13024
Given a set $P$ of points and a set $U$ of axis-parallel unit squares in the Euclidean plane, a minimum ply cover of $P$ with $U$ is a subset of $U$ that covers $P$ and minimizes the number of squares that share a common intersection, called the mini
Externí odkaz:
http://arxiv.org/abs/2208.06122
The burning process on a graph $G$ starts with a single burnt vertex, and at each subsequent step, burns the neighbors of the currently burnt vertices, as well as one other unburnt vertex. The burning number of $G$ is the smallest number of steps req
Externí odkaz:
http://arxiv.org/abs/2205.04643
Publikováno v:
In Theoretical Computer Science 12 January 2025 1024
Chv\'{a}tal and Klincsek (1980) gave an $O(n^3)$-time algorithm for the problem of finding a maximum-cardinality convex subset of an arbitrary given set $P$ of $n$ points in the plane. This paper examines a generalization of the problem, the Bottlene
Externí odkaz:
http://arxiv.org/abs/2108.12464
A grounded 1-bend string graph is an intersection graph of a set of polygonal lines, each with one bend, such that the lines lie above a common horizontal line $\ell$ and have exactly one endpoint on $\ell$. We show that the problem of finding a maxi
Externí odkaz:
http://arxiv.org/abs/2107.05198
Autor:
Bose, Prosenjit, Carmi, Paz, Keil, J. Mark, Maheshwari, Anil, Mehrabi, Saeed, Mondal, Debajyoti, Smid, Michiel
A graph $G$ with $n$ vertices is called an outerstring graph if it has an intersection representation of a set of $n$ curves inside a disk such that one endpoint of every curve is attached to the boundary of the disk. Given an outerstring graph repre
Externí odkaz:
http://arxiv.org/abs/1903.07024