Jacob Holm

Research output

Research output per year 2000 2017 2018 2020

• 9 Article in proceedings
• 3 Journal article
• 1 Ph.D. thesis

Research output per year

Research output per year

Search results

• 2020

  Near-optimal induced universal graphs for cycles and paths

  Abrahamsen, M., Alstrup, S., Holm, J., Knudsen, M. B. T. & Stöckel, M., 15 Aug 2020, In: Discrete Applied Mathematics. 13 p.

  Research output: Contribution to journal › Journal article › Research › peer-review

  • Universal Graphs 100%
  • Moon 77%
  • Decoding 56%
  • Cycle 46%
  • Path 45%
• 2019

  Online Bipartite Matching with Amortized O(log² n) Replacements

  Bernstein, A., Holm, J. & Rotenberg, E., 2019, In: Journal of the ACM. 66, 5, 23 p., 37.

  Research output: Contribution to journal › Journal article › Research › peer-review

  • Network protocols 100%
  • Servers 70%
  3 Citations (Scopus)
• 2018

  Decremental SPQR-trees for planar graphs

  Holm, J., Italiano, G. F., Karczmarz, A., Łacki, J. & Rotenberg, E., 1 Aug 2018, 26th European Symposium on Algorithms, ESA 2018. Bast, H., Herman, G. & Azar, Y. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 112).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Data structures 100%
  2 Citations (Scopus)

• Dynamic bridge-finding in Õ(log² n) amortized time

  Holm, J., Rotenberg, E. & Thorup, M., 2018, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Czumaj, A. (ed.). Society for Industrial and Applied Mathematics, p. 35-52 18 p.

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Update 100%
  • Dynamic Data Structures 80%
  • Perfect Matching 54%
  • Data Structures 52%
  • Linear Space 50%
  6 Citations (Scopus)

• Efficient Graph algorithms and Data Structures

  Holm, J., 2018, Department of Computer Science, Faculty of Science, University of Copenhagen.

  Research output: Book/Report › Ph.D. thesis

• One-way trail orientations

  Aamand, A., Hjuler, N., Holm, J. & Rotenberg, E., 1 Jul 2018, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018. Kaklamanis, C., Marx, D., Chatzigiannakis, I. & Sannella, D. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 6. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 107).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Directed Graph 100%
  • Multigraph 92%
  • Natural Extension 54%
  • Graph in graph theory 49%
  • Mixed Graphs 37%

• Online Bipartite Matching with Amortized Replacements

  Bernstein, A., Holm, J. & Rotenberg, E., 2018, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Czumaj, A. (ed.). Society for Industrial and Applied Mathematics, p. 947-959

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Bipartite Matching 100%
  • Replacement 69%
  • Server 24%
  • Strategy 16%
  • Maximum Matching 14%
  11 Citations (Scopus)
• 2017

  Best laid plans of lions and men

  Abrahamsen, M., Holm, J., Rotenberg, E. & Wulff-Nilsen, C., 2017, 33rd International Symposium on Computational Geometry (SoCG 2017). Aronov, B. & Katz, M. J. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 16 p. 6. (Leibniz International Proceedings in Informatics, Vol. 77).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Units of speed 100%
  • Simple Polygon 65%
  • Pairwise 47%
  • Entire 45%
  • Interior 43%
  30 Downloads (Pure)

• Contracting a planar graph efficiently

  Holm, J., Italiano, G. F., Karczmarz, A., Łacki, J., Rotenberg, E. & Sankowski, P., 1 Sept 2017, 25th European Symposium on Algorithms, ESA 2017. Sohler, C., Sohler, C. & Pruhs, K. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 50. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 87).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Data structures 100%
  • Coloring 35%
  1 Citation (Scopus)

• Dynamic planar embeddings of dynamic graphs

  Holm, J. & Rotenberg, E., Nov 2017, In: Theory of Computing Systems. 61, 4, p. 1054-1083 30 p.

  Research output: Contribution to journal › Journal article › Research › peer-review

  • Dynamic Graphs 100%
  • Flip 51%
  • Spanning tree 46%
  • Query 44%
  • Euler 38%
  3 Citations (Scopus)

• Near-Optimal Induced Universal Graphs for Bounded Degree Graphs

  Abrahamsen, M., Alstrup, S., Holm, J., Knudsen, M. B. T. & Stöckel, M., 1 Jul 2017, 44th International Colloquium on Automata, Languages, and Programming (ICALP 201. Chatzigiannaki, I., Indyk, P., Kuhn, F. & Muscholl, A. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 1-14 128. (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 80).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Universal Graphs 100%
  • Graph in graph theory 30%
  • Geometric Analysis 24%
  • Functional Analysis 20%
  • Upper bound 18%
  1 Citation (Scopus)

  9 Downloads (Pure)
• 2015

  Planar reachability in linear space and constant time

  Holm, J., Rotenberg, E. & Thorup, M., 11 Dec 2015, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, p. 370-389 20 p. (Symposium on Foundations of Computer Science. Annual Proceedings).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Data structures 100%
  6 Citations (Scopus)
• 2000

  Maintaining center and median in dynamic trees

  Alstrup, S., Holm, J. & Thorup, M., 2000, Algorithm Theory-SWAT 2000. Springer Science+Business Media, Vol. 1851. p. 46-56 11 p. (Lecture notes in computer science).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  21 Citations (Scopus)