1 citations · 2 across the 9 of their papers we have counts for
14 papers
Minimum Sum Vertex Cover via Minimum Vertex Cover
Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari +2
The Minimum Sum Vertex Cover (MSVC) problem asks for an ordering of the vertices of a graph that minimizes the sum, over all edges, of the time at which each edge is first covered.…
On 2-Layer k-Matching-Planar Graphs
Saeed Odak, Jonathan Rollin, Torben Scheele
A graph is -matching-planar if it admits a drawing in the plane such that, for every edge , the edges crossing contain no matching of size greater than . The class of…
Shifting is Optimal under Gap-ETH: A Lower Bound Framework for Geometric Approximation Schemes
Manuel Cáceres, Sándor Kisfaludi-Bak, Saeed Odak
The shifting technique of Hochbaum and Maass [J.ACM'85] produces PTASes with the fastest known running times for several -dimensional geometric prob…
Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree
Sándor Kisfaludi-Bak, Saeed Odak, Satyam Singh +1
We give an approximation scheme for the TSP in -dimensional hyperbolic space that has optimal dependence on under Gap-ETH. For any fixed dimension and fo…
Deciding if a DAG is Interesting is Hard
Jean-Lou De Carufel, Anil Maheshwari, Saeed Odak +3
The \emph{interestingness score} of a directed path in an edge-weighted directed graph is defined as $\texttt{score}(Π) := \sum_{i=1}^\ell w(e…
Closest Pair Queries in Vertical Slabs and Tight Bounds on the Number of Possible Answers
Ahmad Biniaz, Prosenjit Bose, Chaeyoon Chung +6
Let be a set of points in , where is a constant, and let be a sequence of vertical hyperplanes that are sorted by their fi…
Computing Oriented Spanners and their Dilation
Kevin Buchin, Antonia Kalb, Anil Maheshwari +4
Given a point set in a metric space and a real number , an \emph{oriented -spanner} is an oriented graph , where for eve…
Contiguous Boundary Guarding
Ahmad Biniaz, Anil Maheshwari, Joseph S. B. Mitchell +3
We study the problem of guarding the boundary of a simple polygon with a minimum number of guards such that each guard covers a contiguous portion of the boundary. First, we presen…
Noncrossing Longest Paths and Cycles
Greg Aloupis, Ahmad Biniaz, Prosenjit Bose +7
Edge crossings in geometric graphs are sometimes undesirable as they could lead to unwanted situations such as collisions in motion planning and inconsistency in VLSI layout. Short…
On -planar Graphs without Short Cycles
Michael A. Bekos, Prosenjit Bose, Aaron Büngener +6
We study the impact of forbidding short cycles to the edge density of -planar graphs; a -planar graph is one that can be drawn in the plane with at most crossings per edg…
On Separating Path and Tree Systems in Graphs
Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel +6
We explore the concept of separating systems of vertex sets of graphs. A separating system of a set is a collection of subsets of such that for any pair of distinct element…
Connected Dominating Sets in Triangulations
Prosenjit Bose, Vida Dujmović, Hussein Houdrouge +2
We show that every -vertex triangulation has a connected dominating set of size at most . Equivalently, every vertex triangulation has a spanning tree with at least…
Odd Colourings of Graph Products
Vida Dujmović, Pat Morin, Saeed Odak
The odd colouring number is a new graph parameter introduced by Petruševski and Škrekovski. In this note, we show that graphs with so called product structure have bounded odd-colo…
A Linear-Time Algorithm for Product Structure in Planar Graphs
Prosenjit Bose, Kaya Gouin, Pat Morin +1
The \emph{Product Structure Theorem} for planar graphs (Dujmović et al.\ \emph{JACM}, \textbf{67}(4):22) states that any planar graph is contained in the strong product of a planar…