3 papers
math.CO2020
Intersecting longest paths in chordal graphs
Daniel J. Harvey, Michael S. Payne
We consider the size of the smallest set of vertices required to intersect every longest path in a chordal graph. Such sets are known as longest path transversals. We show that if…
cs.CG2020
Overlaid oriented Voronoi diagrams and the 1-Steiner tree problem
Michael S. Payne, Charl Ras, Marcus Volz
Overlaid oriented Voronoi diagrams (OOVDs) are known to provide useful data for the construction of optimal Euclidean -Steiner trees. The theoretical time complexity of construc…
math.CO2015
Bichromatic lines in the plane
Michael S. Payne
Given a set of red and blue points in the plane, a bichromatic line is a line containing at least one red and one blue point. We prove the following conjecture of Kleitman and Pinc…