Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Jared Espenant

dblp:289/0895 · DBLP profile ↗
← Back
1ranked-venue papers
1as first author
1since 2021 · last 2023
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 1 · 1 first-author · 1 since 2021

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
1 paper
Computational geometry · 60% Graph algorithms and graph theory · 20% Computational complexity · 20%

Topics — the 5 heaviest of 5, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Computational geometry › intersection graphs
disk graph
0.712023
Finding a Maximum Clique in a Disk Graph · SoCG 2023
Computational geometry › intersection graphs
geometric intersection graphs
0.712023
Finding a Maximum Clique in a Disk Graph · SoCG 2023
Computational complexity
hardness of approximation
0.712023
Finding a Maximum Clique in a Disk Graph · SoCG 2023
Computational geometry
intersection graphs
0.712023
Finding a Maximum Clique in a Disk Graph · SoCG 2023
Graph algorithms and graph theory › graph theory › clique
maximum clique
0.712023
Finding a Maximum Clique in a Disk Graph · SoCG 2023

Methods — techniques the papers use, named apart from their topics

co-2-subdivision · 0.7
YearPublicationVenuePosition
2023 Finding a Maximum Clique in a Disk Graph
abstract
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 complexity of computing a maximum clique in a disk graph is a long-standing open question that has been very well studied in the literature. The problem is known to be open even when the radii of all the disks are in the interval [1,(1+ε)], where ε > 0. If all the disks are unit disks then there exists an O(n³log n)-time algorithm to compute a maximum clique, which is the best-known running time for over a decade. Although the problem of computing a maximum clique in a disk graph remains open, it is known to be APX-hard for the intersection graphs of many other convex objects such as intersection graphs of ellipses, triangles, and a combination of unit disks and axis-parallel rectangles. Here we obtain the following results. - We give an algorithm to compute a maximum clique in a unit disk graph in O(n^2.5 log n)-time, which improves the previously best known running time of O(n³log n) [Eppstein '09]. - We extend a widely used "co-2-subdivision approach" to prove that computing a maximum clique in a combination of unit disks and axis-parallel rectangles is NP-hard to approximate within 4448/4449 ≈ 0.9997. The use of a "co-2-subdivision approach" was previously thought to be unlikely in this setting [Bonnet et al. '20]. Our result improves the previously known inapproximability factor of 7633010347/7633010348 ≈ 0.9999. - We show that the parameter minimum lens width of the disk arrangement may be used to make progress in the case when disk radii are in [1,(1+ε)]. For example, if the minimum lens width is at least 0.265 and ε ≤ 0.0001, which still allows for non-Helly triples in the arrangement, then one can find a maximum clique in polynomial time.
Jared Espenant, J. Mark Keil, Debajyoti Mondal
SoCG1