default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDDavid G. Kirkpatrick
Person information
- affiliation: University of British Columbia, Vancouver, Canada
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[j78]William S. Evans
, David G. Kirkpatrick:
Minimizing Query Frequency to Bound Congestion Potential for Moving Entities at a Fixed Target Time. Algorithms 17(6): 246 (2024)- [j77]David G. Kirkpatrick, Irina Kostitsyna, Alfredo Navarra, Giuseppe Prencipe, Nicola Santoro:
On the power of bounded asynchrony: convergence by autonomous robots with limited visibility. Distributed Comput. 37(3): 279-308 (2024) - 2023
- [j76]Shaun M. Fallat, David G. Kirkpatrick, Hans Ulrich Simon, Abolghasem Soltani, Sandra Zilles:
On Batch Teaching Without Collusion. J. Mach. Learn. Res. 24: 40:1-40:33 (2023) - [c90]William S. Evans, David G. Kirkpatrick:
Minimizing Query Frequency to Bound Congestion Potential for Moving Entities at a Fixed Target Time. FCT 2023: 162-175 - [c89]William S. Evans, David G. Kirkpatrick:
A Frequency-Competitive Query Strategy for Maintaining Low Collision Potential Among Moving Entities. WAOA 2023: 14-28 - 2021
- [c88]David G. Kirkpatrick, Irina Kostitsyna, Alfredo Navarra, Giuseppe Prencipe, Nicola Santoro:
Separating Bounded and Unbounded Asynchrony for Autonomous Robots: Point Convergence with Limited Visibility. PODC 2021: 9-19 - [i7]David G. Kirkpatrick, Irina Kostitsyna, Alfredo Navarra, Giuseppe Prencipe, Nicola Santoro:
Separating Bounded and Unbounded Asynchrony for Autonomous Robots: Point Convergence with Limited Visibility. CoRR abs/2105.13042 (2021) - 2020
- [j75]Anne Condon, Monir Hajiaghayi, David G. Kirkpatrick, Ján Manuch:
Approximate majority analyses using tri-molecular chemical reaction networks. Nat. Comput. 19(1): 249-270 (2020)
2010 – 2019
- 2019
- [c87]David G. Kirkpatrick, Hans Ulrich Simon, Sandra Zilles:
Optimal Collusion-Free Teaching. ALT 2019: 506-528 - [c86]Daniel Busto, William S. Evans, David G. Kirkpatrick:
Minimizing Interference Potential Among Moving Entities. SODA 2019: 2400-2418 - [i6]David G. Kirkpatrick, Hans Ulrich Simon, Sandra Zilles:
Optimal Collusion-Free Teaching. CoRR abs/1903.04012 (2019) - 2018
- [j74]Katsuhisa Yamanaka, Takashi Horiyama, J. Mark Keil, David G. Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno:
Swapping colored tokens on graphs. Theor. Comput. Sci. 729: 1-10 (2018) - [i5]Katsuhisa Yamanaka, Takashi Horiyama, J. Mark Keil, David G. Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno:
Swapping Colored Tokens on Graphs. CoRR abs/1803.06816 (2018) - 2017
- [c85]Ziyuan Gao, David G. Kirkpatrick, Christoph Ries, Hans Ulrich Simon, Sandra Zilles:
Preference-based Teaching of Unions of Geometric Objects. ALT 2017: 185-207 - [c84]Anne Condon, Monir Hajiaghayi, David G. Kirkpatrick, Ján Manuch:
Simplifying Analyses of Chemical Reaction Networks for Approximate Majority. DNA 2017: 188-209 - [c83]Toshiki Saitoh, David G. Kirkpatrick:
Space-Efficient and Output-Sensitive Implementations of Greedy Algorithms on Intervals. WALCOM 2017: 320-332 - 2016
- [j73]William S. Evans, David G. Kirkpatrick, Maarten Löffler, Frank Staals:
Minimizing Co-location Potential of Moving Entities. SIAM J. Comput. 45(5): 1870-1893 (2016) - [c82]Ashwin Gopinath, David G. Kirkpatrick, Paul W. K. Rothemund, Chris Thachuk:
Progressive Alignment of Shapes. CCCG 2016: 230-236 - [c81]David G. Kirkpatrick, Paul Liu:
Characterizing minimum-length coordinated motions for two discs. CCCG 2016: 252-259 - [i4]David G. Kirkpatrick, Paul Liu:
Characterizing minimum-length coordinated motions for two discs. CoRR abs/1607.04005 (2016) - 2015
- [j72]David G. Kirkpatrick:
An O(lg lg OPT)-Approximation Algorithm for Multi-guarding Galleries. Discret. Comput. Geom. 53(2): 327-343 (2015) - [c80]Katsuhisa Yamanaka, Takashi Horiyama, David G. Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno:
Swapping Colored Tokens on Graphs. WADS 2015: 619-628 - 2014
- [j71]David G. Kirkpatrick, Boting Yang, Sandra Zilles:
A Polynomial-Time Algorithm for Computing the Resilience of Arrangements of Ray Sensors. Int. J. Comput. Geom. Appl. 24(3): 225-236 (2014) - [j70]Ellen Gethner, David G. Kirkpatrick, Nicholas Pippenger:
Computational Aspects of M.C. Escher's Ribbon Patterns. Theory Comput. Syst. 54(4): 640-658 (2014) - [j69]David Yu Cheng Chan, David G. Kirkpatrick:
Multi-Path Algorithms for minimum-colour path problems with applications to approximating barrier resilience. Theor. Comput. Sci. 553: 74-90 (2014) - [c79]Tetsuo Asano, David G. Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe:
Õ(√n)-Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability. MFCS (2) 2014: 45-56 - [i3]Tetsuo Asano, David G. Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe:
O(sqrt(n))-Space and Polynomial-time Algorithm for the Planar Directed Graph Reachability Problem. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [c78]David G. Kirkpatrick:
Closing a Long-Standing Complexity Gap for Selection: V 3(42) = 50. Space-Efficient Data Structures, Streams, and Algorithms 2013: 61-76 - [c77]Daniel Busto, William S. Evans, David G. Kirkpatrick:
On k-Guarding Polygons. CCCG 2013 - [c76]William S. Evans, David G. Kirkpatrick, Maarten Löffler, Frank Staals:
Competitive query strategies for minimising the ply of the potential locations of moving points. SoCG 2013: 155-164 - [c75]Sylvester David Eriksson-Bique, David G. Kirkpatrick, Valentin Polishchuk:
On Polygonal Paths with Bounded Discrete-Curvature: The Inflection-Free Case. JCDCGG 2013: 44-64 - [c74]Tetsuo Asano, David G. Kirkpatrick:
Time-Space Tradeoffs for All-Nearest-Larger-Neighbors Problems. WADS 2013: 61-72 - 2012
- [j68]David G. Kirkpatrick:
Guest editorʼs foreword. Comput. Geom. 45(5-6): 199 (2012) - [j67]David G. Kirkpatrick:
Guest Editor's Foreword. Discret. Comput. Geom. 47(4): 659-660 (2012) - [c73]David Yu Cheng Chan, David G. Kirkpatrick:
Approximating Barrier Resilience for Arrangements of Non-identical Disk Sensors. ALGOSENSORS 2012: 42-53 - [c72]Ellen Gethner, David G. Kirkpatrick, Nicholas Pippenger:
M.C. Escher Wrap Artist: Aesthetic Coloring of Ribbon Patterns. FUN 2012: 198-209 - [i2]Sylvester David Eriksson-Bique, David G. Kirkpatrick, Valentin Polishchuk:
Discrete Dubins Paths. CoRR abs/1211.2365 (2012) - 2011
- [j66]James King, David G. Kirkpatrick:
Improved Approximation for Guarding Simple Galleries from the Perimeter. Discret. Comput. Geom. 46(2): 252-269 (2011) - [c71]Kuan-Chieh Robert Tseng, David G. Kirkpatrick:
On Barrier Resilience of Sensor Networks. ALGOSENSORS 2011: 130-144 - [c70]David G. Kirkpatrick, Irina Kostitsyna, Valentin Polishchuk:
Hardness Results for Two-Dimensional Curvature-Constrained Motion Planning. CCCG 2011 - [c69]Victor Alvarez, David G. Kirkpatrick, Raimund Seidel:
Can Nearest Neighbor Searching Be Simple and Always Fast? ESA 2011: 82-92 - [c68]Kuan-Chieh Robert Tseng, David G. Kirkpatrick:
Input-Thrifty Extrema Testing. ISAAC 2011: 554-563 - [c67]David G. Kirkpatrick, Sandra Zilles:
Competitive Search in Symmetric Trees. WADS 2011: 560-570 - 2010
- [j65]Stephane Durocher, David G. Kirkpatrick, Lata Narayanan:
On routing with guaranteed delivery in three-dimensional ad hoc wireless networks. Wirel. Networks 16(1): 227-235 (2010) - [c66]Zohreh Jabbari, William S. Evans, David G. Kirkpatrick:
Multi-guard covers for polygonal regions. CCCG 2010: 5-8 - [c65]David G. Kirkpatrick:
Determining the robustness of sensor barriers. CCCG 2010: 227 - [e1]David G. Kirkpatrick, Joseph S. B. Mitchell:
Proceedings of the 26th ACM Symposium on Computational Geometry, Snowbird, Utah, USA, June 13-16, 2010. ACM 2010, ISBN 978-1-4503-0016-2 [contents] - [i1]James King, David G. Kirkpatrick:
Improved Approximation for Guarding Simple Galleries from the Perimeter. CoRR abs/1001.4231 (2010)
2000 – 2009
- 2009
- [j64]Stephane Durocher, David G. Kirkpatrick:
The projection median of a set of points. Comput. Geom. 42(5): 364-375 (2009) - [j63]Pavol Hell, David G. Kirkpatrick:
Linear-time certifying algorithms for near-graphical sequences. Discret. Math. 309(18): 5703-5713 (2009) - [c64]Sergey Bereg, David G. Kirkpatrick:
Approximating Barrier Resilience in Wireless Sensor Networks. ALGOSENSORS 2009: 29-40 - [c63]Tetsuo Asano, Sergey Bereg, David G. Kirkpatrick:
Finding Nearest Larger Neighbors. Efficient Algorithms 2009: 249-260 - [c62]David G. Kirkpatrick:
Hyperbolic Dovetailing. ESA 2009: 516-527 - 2008
- [j62]Stephane Durocher, David G. Kirkpatrick:
Bounded-Velocity Approximation of Mobile Euclidean 2-Centres. Int. J. Comput. Geom. Appl. 18(3): 161-183 (2008) - [c61]Stephane Durocher, David G. Kirkpatrick, Lata Narayanan:
On Routing with Guaranteed Delivery in Three-Dimensional Ad Hoc Wireless Networks. ICDCN 2008: 546-557 - [c60]Jonathan Backer, David G. Kirkpatrick:
A Complete Approximation Algorithm for Shortest Bounded-Curvature Paths. ISAAC 2008: 628-643 - 2007
- [c59]Jonathan Backer, David G. Kirkpatrick:
Finding curvature-constrained paths that avoid polygonal obstacles. SCG 2007: 66-73 - [c58]Wei-Lung Dustin Tseng, David G. Kirkpatrick:
Lower bounds on average-case delay for video-on-demand broadcast protocols. SODA 2007: 834-842 - 2006
- [j61]Sergey Bereg, Prosenjit Bose, David G. Kirkpatrick:
Equitable subdivisions within polygonal regions. Comput. Geom. 34(1): 20-27 (2006) - [j60]Stephane Durocher, David G. Kirkpatrick:
The Steiner Centre of a Set of Points: Stability, Eccentricity, and Applications to Mobile Facility Location. Int. J. Comput. Geom. Appl. 16(4): 345-372 (2006) - [j59]Sergey Bereg, Binay K. Bhattacharya, David G. Kirkpatrick, Michael Segal:
Competitive Algorithms for Maintaining a Mobile Center. Mob. Networks Appl. 11(2): 177-186 (2006) - [j58]Prosenjit Bose, Luc Devroye, William S. Evans, David G. Kirkpatrick:
On the Spanning Ratio of Gabriel Graphs and beta-Skeletons. SIAM J. Discret. Math. 20(2): 412-427 (2006) - [j57]William S. Evans, David G. Kirkpatrick:
Optimally scheduling video-on-demand to minimize delay when sender and receiver bandwidth may differ. ACM Trans. Algorithms 2(4): 661-678 (2006) - [c57]Jonathan Backer, David G. Kirkpatrick:
Bounded-Curvature Path Normalization. CCCG 2006 - [c56]Tetsuo Asano, David G. Kirkpatrick:
Distance Trisector Curves in Regular Convex Distance Me. ISVD 2006: 8-17 - 2005
- [j56]Daniel Archambault, William S. Evans, David G. Kirkpatrick:
Computing the Set of all the Distant Horizons of a Terrain. Int. J. Comput. Geom. Appl. 15(6): 547-564 (2005) - [c55]Stephane Durocher, David G. Kirkpatrick:
The Projection Median of a Set of Points in R2. CCCG 2005: 47-51 - [c54]Sergey Bereg, David G. Kirkpatrick:
Curvature-bounded traversals of narrow corridors. SCG 2005: 278-287 - 2004
- [j55]Tetsuo Asano, David G. Kirkpatrick, Chee-Keng Yap:
Pseudo Approximation Algorithms with Applications to Optimal Motion Planning. Discret. Comput. Geom. 31(1): 139-171 (2004) - [j54]William S. Evans, David G. Kirkpatrick:
Restructuring ordered binary trees. J. Algorithms 50(2): 168-193 (2004) - [c53]William S. Evans, Daniel Archambault, David G. Kirkpatrick:
Computing the set of all distant horizons of a terrain. CCCG 2004: 76-79 - [c52]Stephane Durocher, David G. Kirkpatrick:
The gaussian centre and the projection centre of a set of points in r3. CCCG 2004: 140-144 - [c51]William S. Evans, David G. Kirkpatrick:
Optimally scheduling video-on-demand to minimize delay when server and receiver bandwidth may differ. SODA 2004: 1041-1049 - 2003
- [j53]Lutz Kettner, David G. Kirkpatrick, Andrea Mantler, Jack Snoeyink, Bettina Speckmann, Fumihiko Takeuchi:
Tight degree bounds for pseudo-triangulations of points. Comput. Geom. 25(1-2): 3-12 (2003) - [j52]Prosenjit Bose, David G. Kirkpatrick, Zaiqing Li:
Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces. Comput. Geom. 26(3): 209-219 (2003) - [c50]Tetsuo Asano, David G. Kirkpatrick, Chee-Keng Yap:
Minimizing the trace length of a rod endpoint in the presence of polygonal obstacles is NP-hard. CCCG 2003: 10-13 - [c49]Stephane Durocher, David G. Kirkpatrick:
The Gaussian Centre of a Set of Mobile Points. CCCG 2003: 123-127 - 2002
- [j51]David G. Kirkpatrick, Jack Snoeyink, Bettina Speckmann:
Kinetic Collision Detection for Simple Polygons. Int. J. Comput. Geom. Appl. 12(1-2): 3-27 (2002) - [j50]Sergei Bespamyatnikh, Binay K. Bhattacharya, J. Mark Keil, David G. Kirkpatrick, Michael Segal:
Efficient algorithms for centers and medians in interval and circular-arc graphs. Networks 39(3): 144-152 (2002) - [c48]Stephane Durocher, David G. Kirkpatrick:
On the hardness of turn-angle-restricted rectilinear cycle cover problems. CCCG 2002: 13-16 - [c47]Francois Anton, David G. Kirkpatrick, Darka Mioc:
An exact algebraic predicate for maintaining the topology of the voronoi diagram for circles. CCCG 2002: 72-76 - [c46]Tetsuo Asano, David G. Kirkpatrick, Chee-Keng Yap:
Pseudo approximation algorithms, with applications to optimal motion planning. SCG 2002: 170-178 - [c45]David G. Kirkpatrick, Bettina Speckmann:
Kinetic maintenance of context-sensitive hierarchical representations for disjoint simple polygons. SCG 2002: 179-188 - [c44]Sergei Bespamyatnikh, Binay K. Bhattacharya, David G. Kirkpatrick, Michael Segal:
Lower and Upper Bounds for Tracking Mobile Users. IFIP TCS 2002: 47-58 - [c43]Sergei Bespamyatnikh, David G. Kirkpatrick:
Constrained Equitable 3-Cuttings. JCDCG 2002: 72-83 - [c42]Prosenjit Bose, Luc Devroye, William S. Evans, David G. Kirkpatrick:
On the Spanning Ratio of Gabriel Graphs and beta-skeletons. LATIN 2002: 479-493 - 2001
- [j49]William S. Evans, David G. Kirkpatrick, G. Townsend:
Right-Triangulated Irregular Networks. Algorithmica 30(2): 264-286 (2001) - [c41]Lutz Kettner, David G. Kirkpatrick, Bettina Speckmann:
Tight degree bounds for pseudo-triangulations of points. CCCG 2001: 117-120 - 2000
- [j48]Sergei Bespamyatnikh, David G. Kirkpatrick, Jack Snoeyink:
Generalizing Ham Sandwich Cuts to Equitable Subdivisions. Discret. Comput. Geom. 24(4): 605-622 (2000) - [c40]David G. Kirkpatrick:
Guarding Alcove-Free Galleries . CCCG 2000 - [c39]David G. Kirkpatrick, Jack Snoeyink, Bettina Speckmann:
Kinetic collision detection for simple polygons. SCG 2000: 322-330 - [c38]Sergei Bespamyatnikh, Binay K. Bhattacharya, David G. Kirkpatrick, Michael Segal:
Mobile facility location. DIAL-M 2000: 46-53 - [c37]Sergei Bespamyatnikh, Binay K. Bhattacharya, J. Mark Keil, David G. Kirkpatrick, Michael Segal:
Efficient Algorithms for Centers and Medians in Interval and Circular-Arc Graphs. ESA 2000: 100-111 - [c36]David G. Kirkpatrick, Bettina Speckmann:
Separation Sensitive Kinetic Separation Structures for Convex Polygons. JCDCG 2000: 222-236 - [c35]William S. Evans, David G. Kirkpatrick:
Restructuring ordered binary trees. SODA 2000: 477-486
1990 – 1999
- 1999
- [j47]David G. Kirkpatrick, Jack Snoeyink:
Computing Constrained Shortest Segments: Butterfly Wingspans in Logarithmic Time. Int. J. Comput. Geom. Appl. 9(1): 53-62 (1999) - [c34]Sergei Bespamyatnikh, David G. Kirkpatrick:
Rectilinear 2-center problems. CCCG 1999 - [c33]Sergei Bespamyatnikh, David G. Kirkpatrick, Jack Snoeyink:
Generalizing Ham Sandwich Cuts to Equitable Subdivisions. SCG 1999: 49-58 - 1998
- [j46]Heinz Breu, David G. Kirkpatrick:
Unit disk graph recognition is NP-hard. Comput. Geom. 9(1-2): 3-24 (1998) - [j45]David G. Kirkpatrick, Madhukar K. Reddy, C. Pandu Rangan, Anand Srinivasan:
Partial and Perfect Path Covers of Cographs. Discret. Appl. Math. 89(1-3): 143-153 (1998) - 1997
- [j44]Lisa Higham, David G. Kirkpatrick, Karl R. Abrahamson, Andrew Adler:
Optimal Algorithms for Probabilistic Solitude Detection on Anonymous Rings. J. Algorithms 23(2): 291-328 (1997) - 1996
- [j43]David G. Kirkpatrick, Teresa M. Przytycka:
Parallel Construction of Binary Trees with Near Optimal Weighted Path Lengt. Algorithmica 15(2): 172-192 (1996) - [j42]David G. Kirkpatrick, Stephen K. Wismath:
Determining Bar-representability for Ordered Weighted Graphs. Comput. Geom. 6: 99-122 (1996) - [j41]Pavol Hell, David G. Kirkpatrick, Brenda Li:
Rounding in Symmetric Matrices and Undirected Graphs. Discret. Appl. Math. 70(1): 1-21 (1996) - [j40]Michael McAllister, David G. Kirkpatrick, Jack Snoeyink:
A Compact Piecewise-Linear Voronoi Diagram for Convex Sites in the Plane. Discret. Comput. Geom. 15(1): 73-105 (1996) - [c32]Prosenjit Bose, William S. Evans, David G. Kirkpatrick, Michael McAllister, Jack Snoeyink:
Approximating Shortest Paths in Arrangements of Lines. CCCG 1996: 143-148 - [c31]Prosenjit Bose, David G. Kirkpatrick, Zaiqing Li:
Efficient Algorithms for Guarding or Illuminating the Surface of a Polyhedral Terrain. CCCG 1996: 217-222 - [c30]Tetsuo Asano, David G. Kirkpatrick, Chee-Keng Yap:
d1-Optimal Motion for a Rod (Extended Abstract). SCG 1996: 252-263 - 1995
- [j39]David G. Kirkpatrick, Jack Snoeyink:
Tentative Prune-and-Search for Computing Fixed-Points with Applications to Geometric Computation. Fundam. Informaticae 22(4): 353-370 (1995) - [j38]Heinz Breu, Joseph Gil, David G. Kirkpatrick, Michael Werman:
Linear Time Euclidean Distance Algorithms. IEEE Trans. Pattern Anal. Mach. Intell. 17(5): 529-533 (1995) - [c29]Heinz Breu, David G. Kirkpatrick:
On the Complexity of Recognizing Intersection and Touching Graphs of Disks. GD 1995: 88-98 - [c28]David G. Kirkpatrick, Jack Snoeyink:
Computing Common Tangents Without a Separating Line. WADS 1995: 183-193 - 1994
- [j37]Karl R. Abrahamson, Andrew Adler, Lisa Higham, David G. Kirkpatrick:
Tight Lower Bounds for Probabilistic Solitude Verification on Anonymous Rings. J. ACM 41(2): 277-310 (1994) - 1993
- [j36]David P. Dobkin, John Hershberger, David G. Kirkpatrick, Subhash Suri:
Computing the Intersection-Depth of Polyhedra. Algorithmica 9(6): 518-533 (1993) - [j35]Feng Gao, Leonidas J. Guibas, David G. Kirkpatrick, William T. Laaser, James B. Saxe:
Finding Extrema with Unary Predicates. Algorithmica 9(6): 591-600 (1993) - [j34]Pavol Hell, David G. Kirkpatrick:
Algorithms for Degree Constrained Graph Factors of Minimum Deficiency. J. Algorithms 14(1): 115-138 (1993) - [c27]David G. Kirkpatrick, Jack Snoeyink:
Computing Constrained Shortest Segments: Butterfly Wingspans in Logarithmic Time. CCCG 1993: 163-168 - [c26]David G. Kirkpatrick, Jack Snoeyink:
Tentative Prune-and-Search for Computing Voronoi Vertices. SCG 1993: 133-142 - [c25]Michael McAllister, David G. Kirkpatrick, Jack Snoeyink:
A Compact Piecewise-Linear Voronoi Diagram for Convex Sites in the Plane. FOCS 1993: 573-582 - 1992
- [j33]David G. Kirkpatrick, Bhubaneswar Mishra, Chee-Keng Yap:
Quantitative Steinitz's Theorems Applications to Multifingered Grasping. Discret. Comput. Geom. 7: 295-318 (1992) - [j32]David G. Kirkpatrick, Maria M. Klawe, Robert Endre Tarjan:
Polygon Triangulation in O (n log log n) Time with Simple Data Structures. Discret. Comput. Geom. 7: 329-346 (1992) - 1991
- [c24]Karl R. Abrahamson, Andrew Adler, Lisa Higham, David G. Kirkpatrick:
Probabilistic Leader Election on Rings of Known Size. WADS 1991: 481-495 - 1990
- [j31]Norm Dadoun, David G. Kirkpatrick:
Parallel algorithms for fractional and maximal independent sets in planar graphs. Discret. Appl. Math. 27(1-2): 69-83 (1990) - [j30]David G. Kirkpatrick, Teresa M. Przytycka:
Parallel recognition of complement reducible graphs and cotree construction. Discret. Appl. Math. 29(1): 79-96 (1990) - [j29]Katherine Heinrich, Pavol Hell, David G. Kirkpatrick, Guizhen Liu:
A simple existence criterion for (g<f)- factors. Discret. Math. 85(3): 313-317 (1990) - [c23]David G. Kirkpatrick, Maria M. Klawe, Robert Endre Tarjan:
Polygon Triangulation in O(n log log n) Time with Simple Data-Structures. SCG 1990: 34-43 - [c22]David P. Dobkin, David G. Kirkpatrick:
Determining the Separation of Preprocessed Polyhedra - A Unified Approach. ICALP 1990: 400-413 - [c21]David G. Kirkpatrick, Feng Gao:
Finding Extrema with Unary Predicates. SIGAL International Symposium on Algorithms 1990: 156-164 - [c20]David P. Dobkin, John Hershberger, David G. Kirkpatrick, Subhash Suri:
Implicitly Searching Convolutions and Computing Depth of Collision. SIGAL International Symposium on Algorithms 1990: 165-180 - [c19]David G. Kirkpatrick, Teresa M. Przytycka:
Parallel Construction of near Optimal binary Trees. SPAA 1990: 234-243 - [c18]David G. Kirkpatrick, Teresa M. Przytycka:
An optimal parallel minimax tree algorithm. SPDP 1990: 293-300 - [c17]David G. Kirkpatrick, Bhubaneswar Mishra, Chee-Keng Yap:
Quantitative Steinitz's Theorems with Applications to Multifingered Grasping. STOC 1990: 341-351
1980 – 1989
- 1989
- [j28]Karl R. Abrahamson, Andrew Adler, Lisa Higham, David G. Kirkpatrick:
Randomized Function Evaluation on a Ring. Distributed Comput. 3(3): 107-117 (1989) - [j27]Karl R. Abrahamson, Norm Dadoun, David G. Kirkpatrick, Teresa M. Przytycka:
A Simple Parallel Tree Contraction Algorithm. J. Algorithms 10(2): 287-302 (1989) - [j26]Norm Dadoun, David G. Kirkpatrick:
Parallel Construction of Subdivision Hierarchies. J. Comput. Syst. Sci. 39(2): 153-165 (1989) - [j25]Karl R. Abrahamson, Andrew Adler, Rachel Gelbart, Lisa Higham, David G. Kirkpatrick:
The Bit Complexity of Randomized Leader Election on a Ring. SIAM J. Comput. 18(1): 12-29 (1989) - [c16]Binay K. Bhattacharya, David G. Kirkpatrick, Godfried T. Toussaint:
Determining Sector Visibility of a Polygon. SCG 1989: 247-253 - [c15]David G. Kirkpatrick, Stephen K. Wismath:
Weighted Visibility Graphs of Bars and Related Flow Problems (Extended Abstract). WADS 1989: 325-334 - 1988
- [j24]David G. Kirkpatrick:
Establishing Order in Planar Subdivisions. Discret. Comput. Geom. 3: 267-280 (1988) - [j23]Michael Kaminski, David G. Kirkpatrick, Nader H. Bshouty:
Addition Requirements for Matrix and Transposed Matrix Products. J. Algorithms 9(3): 354-364 (1988) - [j22]Pavol Hell, David G. Kirkpatrick, Jan Kratochvíl, Igor Kríz:
On Restricted Two-Factors. SIAM J. Discret. Math. 1(4): 472-484 (1988) - 1987
- [c14]Norm Dadoun, David G. Kirkpatrick:
Parallel Processing for Efficient Subdivision Search. SCG 1987: 205-214 - [c13]David G. Kirkpatrick:
Establishing Order in Planar Subdivisions. SCG 1987: 316-321 - [c12]Karl R. Abrahamson, Andrew Adler, Lisa Higham, David G. Kirkpatrick:
Randomized Function on a Ring (Preliminary Version). WDAG 1987: 324-331 - 1986
- [j21]Pierre Fraisse, Pavol Hell, David G. Kirkpatrick:
A note onf-factors in directed and undirected multigraphs. Graphs Comb. 2(1): 61-66 (1986) - [j20]David G. Kirkpatrick, Raimund Seidel:
The Ultimate Planar Convex Hull Algorithm? SIAM J. Comput. 15(1): 287-299 (1986) - [c11]Karl R. Abrahamson, Andrew Adler, Lisa Higham, David G. Kirkpatrick:
Probabilistic Solitude Verification on a Ring. PODC 1986: 161-173 - 1985
- [j19]David P. Dobkin, David G. Kirkpatrick:
A Linear Algorithm for Determining the Separation of Convex Polyhedra. J. Algorithms 6(3): 381-392 (1985) - [j18]David G. Kirkpatrick, Maria M. Klawe:
Alphabetic Minimax Trees. SIAM J. Comput. 14(3): 514-526 (1985) - [c10]Norm Dadoun, David G. Kirkpatrick, John P. Walsh:
The geometry of beam tracing. SCG 1985: 55-61 - [c9]David G. Kirkpatrick, Raimund Seidel:
Output-size sensitive algorithms for finding maximal vectors. SCG 1985: 89-96 - 1984
- [j17]Pavol Hell, David G. Kirkpatrick:
Packings by cliques and by finite families of graphs. Discret. Math. 49(1): 45-59 (1984) - [j16]David G. Kirkpatrick, Stefan Reisch:
Upper Bounds for Sorting Integers on Random Access Machines. Theor. Comput. Sci. 28: 263-276 (1984) - 1983
- [j15]David G. Kirkpatrick, Maria M. Klawe, Derek G. Corneil:
On pseudosimilarity in trees. J. Comb. Theory B 34(3): 323-339 (1983) - [j14]David G. Kirkpatrick:
Optimal Search in Planar Subdivisions. SIAM J. Comput. 12(1): 28-35 (1983) - [j13]David G. Kirkpatrick, Pavol Hell:
On the Complexity of General Graph Factor Problems. SIAM J. Comput. 12(3): 601-609 (1983) - [j12]David P. Dobkin, David G. Kirkpatrick:
Fast Detection of Polyhedral Intersection. Theor. Comput. Sci. 27: 241-253 (1983) - [j11]Herbert Edelsbrunner, David G. Kirkpatrick, Raimund Seidel:
On the shape of a set of points in the plane. IEEE Trans. Inf. Theory 29(4): 551-558 (1983) - [j10]I. G. Gowda, David G. Kirkpatrick, D. T. Lee, Amnon Naamad:
Dynamic Voronoi diagrams. IEEE Trans. Inf. Theory 29(5): 724-730 (1983) - 1982
- [j9]Herbert Edelsbrunner, Hermann A. Maurer, David G. Kirkpatrick:
Polygonal Intersection Searching. Inf. Process. Lett. 14(2): 74-79 (1982) - [c8]David P. Dobkin, David G. Kirkpatrick:
Fast Detection of Polyhedral Intersections. ICALP 1982: 154-165 - [c7]Doron Rotem, Frank Wm. Tompa, David G. Kirkpatrick:
Foundations for Multifile Design by Application Partitioning. PODS 1982: 262-267 - 1981
- [j8]Pavol Hell, David G. Kirkpatrick:
On Generalized Matching Problems. Inf. Process. Lett. 12(1): 33-35 (1981) - [j7]David G. Kirkpatrick:
A Unified Lower Bound for Selection and Set Partitioning Problems. J. ACM 28(1): 150-165 (1981) - [j6]Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, Martin Tompa:
A Time-Space Tradeoff for Sorting on Non-Oblivious Machines. J. Comput. Syst. Sci. 22(3): 351-364 (1981) - [j5]David G. Kirkpatrick, Derek G. Corneil:
Forest embeddings in regular graphs of large girth. J. Comb. Theory B 30(1): 45-60 (1981) - [c6]Herbert Edelsbrunner, David G. Kirkpatrick, Raimund Seidel:
The Shape of a Set of Points in the Plane. WG 1981: 157-162 - 1980
- [j4]David G. Kirkpatrick:
A Note on Delaunay and Optimal Triangulations. Inf. Process. Lett. 10(3): 127-128 (1980) - [j3]Derek G. Corneil, David G. Kirkpatrick:
A Theoretical Analysis of Various Heuristics for the Graph Isomorphism Problem. SIAM J. Comput. 9(2): 281-297 (1980)
1970 – 1979
- 1979
- [j2]Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, Martin Tompa:
A time-space tradeoff for sorting and related non-oblivious computations. SIGACT News 11(2): 24 (1979) - [c5]David G. Kirkpatrick:
Efficient Computation of Continuous Skeletons. FOCS 1979: 18-27 - [c4]Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, Martin Tompa:
A Time-Space Tradeoff for Sorting on Non-Oblivious Machines. FOCS 1979: 319-327 - 1978
- [c3]David G. Kirkpatrick, Pavol Hell:
On the Completeness of a Generalized Matching Problem. STOC 1978: 240-245 - 1977
- [j1]David G. Kirkpatrick, Zvi M. Kedem:
Adequate Requirements for Rational Functions. SIAM J. Comput. 6(1): 188-199 (1977) - 1974
- [c2]David G. Kirkpatrick:
Determining Graph Properties from Matrix Representations. STOC 1974: 84-90 - 1972
- [c1]David G. Kirkpatrick:
On the Additions Necessary to Compute Certain Functions. STOC 1972: 94-101
Coauthor Index
Sergey Bereg
aka: Sergei Bespamyatnikh
aka: Sergei Bespamyatnikh
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-01-21 00:08 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
