7 citations · 9 across the 5 of their papers we have counts for
4 papers · 1 filter
The Simultaneous Membership Problem for Chordal, Comparability and Permutation graphs
Krishnam Raju Jampani, Anna Lubiw
In this paper we introduce the 'simultaneous membership problem', defined for any graph class C characterized in terms of representations, e.g. any class of intersection graphs. Tw…
Shortest Paths Avoiding Forbidden Subpaths
Mustaq Ahmed, Anna Lubiw
In this paper we study a variant of the shortest path problem in graphs: given a weighted graph G and vertices s and t, and given a set X of forbidden paths in G, find a shortest s…
Approximation Algorithms for Shortest Descending Paths in Terrains
Mustaq Ahmed, Sandip Das, Sachin Lodha +3
A path from s to t on a polyhedral terrain is descending if the height of a point p never increases while we move p along the path from s to t. No efficient algorithm is known to f…
A Lower Bound on the Area of a 3-Coloured Disk Packing
Peter Brass, Ferran Hurtado, Benjamin Lafreniere +1
Given a set of unit-disks in the plane with union area , what fraction of can be covered by selecting a pairwise disjoint subset of the disks? Rado conjectured 1/4 and prove…