J. Mark Keil

According to our database, J. Mark Keil authored at least 66 papers between 1983 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2025

Approximation algorithms for minimum ply covering of points with unit squares and unit disks.

Stephane Durocher, J. Mark Keil, Debajyoti Mondal

Theor. Comput. Sci., 2025

2024

Quantum Speedup for Some Geometric 3SUM-Hard Problems and Beyond.

J. Mark Keil, Fraser McLeod, Debajyoti Mondal

CoRR, 2024

The Maximum Clique Problem in a Disk Graph Made Easy.

J. Mark Keil, Debajyoti Mondal

CoRR, 2024

2023

Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set.

Stephane Durocher, J. Mark Keil, Saeed Mehrabi, Debajyoti Mondal

Int. J. Comput. Geom. Appl., 2023

Improved and Generalized Algorithms for Burning a Planar Point Set.

Prashant Gokhale, J. Mark Keil, Debajyoti Mondal

Proceedings of the WALCOM: Algorithms and Computation, 2023

Minimum Ply Covering of Points with Unit Squares.

Stephane Durocher, J. Mark Keil, Debajyoti Mondal

Proceedings of the WALCOM: Algorithms and Computation, 2023

Finding a Maximum Clique in a Disk Graph.

Jared Espenant, J. Mark Keil, Debajyoti Mondal

Proceedings of the 39th International Symposium on Computational Geometry, 2023

Minimum Ply Covering of Points with Unit Disks.

Stephane Durocher, J. Mark Keil, Debajyoti Mondal

Proceedings of the 35th Canadian Conference on Computational Geometry, 2023

2022

Finding a Maximum Clique in a Grounded 1-Bend String Graph.

J. Mark Keil, Debajyoti Mondal, Ehsan Moradi, Yakov Nekrich

J. Graph Algorithms Appl., 2022

Computing maximum independent set on outerstring graphs and their relatives.

Prosenjit Bose, Paz Carmi, J. Mark Keil, Anil Maheshwari, Saeed Mehrabi, Debajyoti Mondal, Michiel Smid

Comput. Geom., 2022

Burning Number for the Points in the Plane.

J. Mark Keil, Debajyoti Mondal, Ehsan Moradi

Proceedings of the 34th Canadian Conference on Computational Geometry, 2022

2020

Finding a Maximum Clique in a Grounded 1-Bend String Graph.

J. Mark Keil, Debajyoti Mondal, Ehsan Moradi

Proceedings of the 32nd Canadian Conference on Computational Geometry, 2020

2019

Perfect Roman domination in graphs.

S. Banerjee, J. Mark Keil, Dinabandhu Pradhan

Theor. Comput. Sci., 2019

Polygon simplification by minimizing convex corners.

Yeganeh Bahoo, Stephane Durocher, J. Mark Keil, Debajyoti Mondal, Saeed Mehrabi, Sahar Mehrpour

Theor. Comput. Sci., 2019

2018

Swapping colored tokens on graphs.

Katsuhisa Yamanaka, Takashi Horiyama, J. Mark Keil, David G. Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno

Theor. Comput. Sci., 2018

Boundary Labeling for Rectangular Diagrams.

Prosenjit Bose, Paz Carmi, J. Mark Keil, Saeed Mehrabi, Debajyoti Mondal

Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

2017

An algorithm for the maximum weight independent set problem on outerstring graphs.

J. Mark Keil, Joseph S. B. Mitchell, Dinabandhu Pradhan, Martin Vatshelle

Comput. Geom., 2017

2015

An Algorithm for the Maximum Weight Independent Set Problem onOutersting Graphs.

J. Mark Keil, Joseph S. B. Mitchell, Dinabandhu Pradhan, Martin Vatshelle

Proceedings of the 27th Canadian Conference on Computational Geometry, 2015

2013

Computing a minimum outer-connected dominating set for the class of chordal graphs.

J. Mark Keil, Dinabandhu Pradhan

Inf. Process. Lett., 2013

2010

Algorithmic properties of ciliate sequence alignment.

J. Mark Keil, Jing Liu, Ian McQuillan

Theor. Comput. Sci., 2010

Constant factor approximation algorithms for the densest k-subgraph problem on proper interval graphs and bipartite permutation graphs.

Jonathan Backer, J. Mark Keil

Inf. Process. Lett., 2010

The Mono- and Bichromatic Empty Rectangle and Square Problems in All Dimensions.

Jonathan Backer, J. Mark Keil

Proceedings of the LATIN 2010: Theoretical Informatics, 2010

2009

The Bichromatic Rectangle Problem in High Dimensions.

Jonathan Backer, J. Mark Keil

Proceedings of the 21st Annual Canadian Conference on Computational Geometry, 2009

2008

The relative neighbourhood graph is a part of every 30degree-triangulation.

J. Mark Keil, Tzvetalin S. Vassilev

Inf. Process. Lett., 2008

2007

Polygon Decomposition and the Orthogonal Art Gallery Problem.

Chris Worman, J. Mark Keil

Int. J. Comput. Geom. Appl., 2007

2006

Approximating the minimum clique cover and other hard problems in subtree filament graphs.

J. Mark Keil, Lorna Stewart

Discret. Appl. Math., 2006

Algorithms for optimal area triangulations of a convex polygon.

J. Mark Keil, Tzvetalin S. Vassilev

Comput. Geom., 2006

On the Stretch Factor of the Constrained Delaunay Triangulation.

Prosenjit Bose, J. Mark Keil

Proceedings of the 3rd International Symposium on Voronoi Diagrams in Science and Engineering, 2006

Routing Properties of the Localized Delaunay Triangulation over Heterogeneous Ad-Hoc Wireless Networks.

Mark D. Watson, J. Mark Keil

Proceedings of the Computational Science and Its Applications, 2006

2005

The relative neighbourhood graph is a part of every 30°-triangulation.

J. Mark Keil, Tzvetalin S. Vassilev

Proceedings of the (Informal) Proceedings of the 21st European Workshop on Computational Geometry, 2005

2004

Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs.

J. Mark Keil, Patrice Belleville

Discret. Appl. Math., 2004

Computing a (1+epsilon)-Approximate Geometric Minimum-Diameter Spanning Tree.

Michael J. Spriggs, J. Mark Keil, Sergei Bespamyatnikh, Michael Segal, Jack Snoeyink

Algorithmica, 2004

2003

Approximating the geometric minimum-diameter spanning tree.

Michael J. Spriggs, J. Mark Keil, Sergei Bespamyatnikh, Michael Segal, Jack Snoeyink

Proceedings of the 15th Canadian Conference on Computational Geometry, 2003

An algorithm for the MaxMin area triangulation of a convex polygon.

J. Mark Keil, Tzvetalin S. Vassilev

Proceedings of the 15th Canadian Conference on Computational Geometry, 2003

2002

Efficient algorithms for centers and medians in interval and circular-arc graphs.

Sergei Bespamyatnikh, Binay K. Bhattacharya, J. Mark Keil, David G. Kirkpatrick, Michael Segal

Networks, 2002

A new bound for map labeling with uniform circle pairs.

Michael J. Spriggs, J. Mark Keil

Inf. Process. Lett., 2002

On the Time Bound for Convex Decomposition of Simple Polygons.

J. Mark Keil, Jack Snoeyink

Int. J. Comput. Geom. Appl., 2002

2000

Visibility Stabs and Depth-First Spiralling on Line Segments in Output Sensitive Time.

J. Mark Keil, David M. Mount, Stephen K. Wismath

Int. J. Comput. Geom. Appl., 2000

Polygon Decomposition.

J. Mark Keil

Proceedings of the Handbook of Computational Geometry, 2000

1999

Minimum spanning trees on polyhedra.

Michael J. Spriggs, J. Mark Keil

Proceedings of the 11th Canadian Conference on Computational Geometry, 1999

1997

Covering Orthogonal Polygons with Non-Piercing Rectangles.

J. Mark Keil

Int. J. Comput. Geom. Appl., 1997

Computing Visibility Information in an Inaccurate Simple Polygon.

Leizhen Cai, J. Mark Keil

Int. J. Comput. Geom. Appl., 1997

A Large Subgraph of the Minimum Weight Triangulation.

Matthew Dickerson, J. Mark Keil, Mark H. Montague

Discret. Comput. Geom., 1997

1996

Two Minimum Dominating Sets with Minimum Intersection in Chordal Graphs.

Peter Eades, J. Mark Keil, Paul D. Manuel, Mirka Miller

Nord. J. Comput., 1996

On Computing Edges That Are In All Minimum-Weight Triangulations.

Patrice Belleville, J. Mark Keil, Michael McAllister, Jack Snoeyink

Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

1994

Spanners in graphs of bounded degree.

Leizhen Cai, J. Mark Keil

Networks, 1994

Computing a Subgraph of the Minimum Weight Triangulation.

J. Mark Keil

Comput. Geom., 1994

1993

Degree-Bounded Spanners.

Leizhen Cai, J. Mark Keil

Parallel Process. Lett., 1993

The Complexity of Domination Problems in Circle Graphs.

J. Mark Keil

Discret. Appl. Math., 1993

1992

On the complexity of scheduling tasks with discrete starting times.

J. Mark Keil

Oper. Res. Lett., 1992

On covering orthogonal polygons with star-shaped polygons.

Laxmi P. Gewali, J. Mark Keil, Simeon C. Ntafos

Inf. Sci., 1992

Efficient Algorithms for the Capacitated 1-Median Problem.

Hossam ElGindy, J. Mark Keil

INFORMS J. Comput., 1992

Classes of Graphs Which Approximate the Complete Euclidean Graph.

J. Mark Keil, Carl A. Gutwin

Discret. Comput. Geom., 1992

An optimal algorithm for finding dominating cycles in circular-arc graphs.

J. Mark Keil, Doug Schaefer

Discret. Appl. Math., 1992

1991

A Simple Algorithm for Determining the Envelope of a Set of Lines.

J. Mark Keil

Inf. Process. Lett., 1991

1989

Polynomial algorithms for restricted Euclidean p-centre problems.

Larry Aupperle, J. Mark Keil

Discret. Appl. Math., 1989

The Delauney Triangulation Closely Approximates the Complete Euclidean Graph.

J. Mark Keil, Carl A. Gutwin

Proceedings of the Algorithms and Data Structures, 1989

1988

Approximating the Complete Euclidean Graph.

J. Mark Keil

Proceedings of the SWAT 88, 1988

Clustering Algorithms Based on Minimum and Maximum Spanning Trees.

Tetsuo Asano, Binay K. Bhattacharya, J. Mark Keil, F. Frances Yao

Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

1986

Total Domination in Interval Graphs.

J. Mark Keil

Inf. Process. Lett., 1986

Minimally Covering a Horizontally Convex Orthogonal Polygon.

J. Mark Keil

Proceedings of the Second Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry, 1986

1985

Decomposing a Polygon into Simpler Components.

J. Mark Keil

SIAM J. Comput., 1985

Domination in Permutation Graphs.

Martin Farber, J. Mark Keil

J. Algorithms, 1985

Finding Hamiltonian Circuits in Interval Graphs.

J. Mark Keil

Inf. Process. Lett., 1985

1983

Decomposing polygons into simpler components.

J. Mark Keil

PhD thesis, 1983

A note on a conjecture by Gavril on clique separable graphs.

Derek G. Corneil, J. Mark Keil

Discret. Math., 1983