Shiri Chechik

Research output

Research output per year 2009 2010 2012 2013 2014 2015 2016 2017 2018 2019 2020 2022 2022

• 52 Conference contribution
• 13 Article
• 2 Paper
• 1 Editorial

Research output per year

Research output per year

Search results

• 2022

  Constant Approximation of Min-Distances in Near-Linear Time

  Chechik, S. & Zhang, T., 2022, Proceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022. IEEE Computer Society, p. 896-906 11 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2022-October).

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

  • Approximation algorithms 100%
  • Directed graphs 53%
  • Blow molding 50%
  • Hardness 36%

• Constant-Round Near-Optimal Spanners in Congested Clique

  Chechik, S. & Zhang, T., 20 Jul 2022, PODC 2022 - Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery, p. 325-334 10 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

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

  • Graph algorithms 100%

• Nearly 2-Approximate Distance Oracles in Subquadratic Time

  Chechik, S. & Zhang, T., 2022, ACM-SIAM Symposium on Discrete Algorithms, SODA 2022. Association for Computing Machinery, p. 551-580 30 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2022-January).

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

  • Oracle 100%
  • Stretch 71%
  • Data structures 39%
  • Preprocessing 27%
  • Beat 15%
• 2021

  Incremental single source shortest paths in sparse digraphs

  Chechik, S. & Zhang, T., 2021, ACM-SIAM Symposium on Discrete Algorithms, SODA 2021. Marx, D. (ed.). Association for Computing Machinery, p. 2463-2477 15 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

  • Shortest path 100%
  • Digraph 88%
  • Update 74%
  • Sparse Graphs 44%
  • Deterministic Algorithm 43%

• Optimal girth approximation for dense directed graphs

  Chechik, S. & Lifshitz, G., 2021, ACM-SIAM Symposium on Discrete Algorithms, SODA 2021. Marx, D. (ed.). Association for Computing Machinery, p. 290-300 11 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

  • Directed graphs 100%
  • Girth 90%
  • Directed Graph 80%
  • Approximation 43%
  • Spanners 38%
• 2020

  Constant girth approximation for directed graphs in subquadratic time

  Chechik, S., Liu, Y. P., Rotem, O. & Sidford, A., 8 Jun 2020, STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G. & Chuzhoy, J. (eds.). Association for Computing Machinery, p. 1010-1023 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

  • Directed graphs 100%

• Distance sensitivity oracles with subcubic preprocessing time and fast query time

  Chechik, S. & Cohen, S., 8 Jun 2020, STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G. & Chuzhoy, J. (eds.). Association for Computing Machinery, p. 1375-1388 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

  • Directed graphs 100%
  • Polynomials 66%

• Dynamic low-stretch spanning trees in subpolynomial time

  Chechik, S. & Zhang, T., 2020, 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020. Chawla, S. (ed.). Association for Computing Machinery, p. 463-475 13 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2020-January).

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

  • Stretch 100%
  • Spanning tree 84%
  • Dynamic Algorithms 48%
  • Weighted Graph 34%
  • Update 32%

• Near optimal algorithm for the directed single source replacement paths problem

  Chechik, S. & Magen, O., 1 Jun 2020, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020. Czumaj, A., Dawar, A. & Merelli, E. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 81. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 168).

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

• Simplifying and unifying replacement paths algorithms in weighted directed graphs

  Chechik, S. & Nechushtan, M., 1 Jun 2020, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020. Czumaj, A., Dawar, A. & Merelli, E. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 29. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 168).

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

  • Directed graphs 100%

• Single-Source Shortest Paths in the CONGEST Model with Improved Bound

  Chechik, S. & Mukhtar, D., 31 Jul 2020, PODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing. Association for Computing Machinery, p. 464-473 10 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

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

  • Directed graphs 100%
  • Distributed computer systems 90%
• 2019

  Deterministic combinatorial replacement paths and distance sensitivity oracles

  Alon, N., Chechik, S. & Cohen, S., 1 Jul 2019, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. Baier, C., Chatzigiannakis, I., Flocchini, P. & Leonardi, S. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 12. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 132).

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

  • Directed graphs 100%
  • Graph algorithms 53%
  • Data structures 35%

• Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time

  Chechik, S. & Zhang, T., Nov 2019, Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019. IEEE Computer Society, p. 370-381 12 p. 8948632. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2019-November).

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

• Reachability and shortest paths in the broadcast congest model

  Chechik, S. & Mukhtar, D., Oct 2019, 33rd International Symposium on Distributed Computing, DISC 2019. Suomela, J. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 11. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 146).

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

  • Directed graphs 100%
  • Parallel algorithms 26%
• 2018

  Clustering small samples with quality guarantees: Adaptivity with One2ALL PPs

  Cohen, E., Chechik, S. & Kaplan, H., 2018, 32nd AAAI Conference on Artificial Intelligence, AAAI 2018. AAAI press, p. 2884-2891 8 p. (32nd AAAI Conference on Artificial Intelligence, AAAI 2018).

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

  • Costs 100%
  • Clustering algorithms 47%
  • Set theory 33%

• Dynamic matching: Reducing integral algorithms to approximately-maximal fractional algorithms

  Arar, M., Chechik, S., Cohen, S., Stein, C. & Wajc, D., 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, 7. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 107).

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

  • Polynomials 100%

• Incremental topological sort and cycle detection in Õ (m √n) expected total time

  Bernstein, A. & Chechik, S., 2018, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. Czumaj, A. (ed.). Association for Computing Machinery, p. 21-34 14 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

  Open Access

  • Sort 100%
  • Cycle 69%
  • Graph algorithms 24%
  • Update 24%
  • Directed graphs 23%

• Near-optimal approximate decremental all pairs shortest paths

  Chechik, S., 30 Nov 2018, Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018. Thorup, M. (ed.). IEEE Computer Society, p. 170-181 12 p. 8555103. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2018-October).

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

• Ramsey spanning trees and their applications

  Abraham, I., Chechik, S., Elkin, M., Filtser, A. & Neiman, O., 2018, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. Czumaj, A. (ed.). Association for Computing Machinery, p. 1650-1664 15 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

  Open Access

  • Spanning tree 100%
  • Hilbert spaces 65%
  • Spanner 65%
  • Stretch 58%
  • Labels 41%
• 2017

  (1 + ϵ)-Approximate f-sensitive distance oracles

  Chechik, S., Cohen, S., Fiat, A. & Kaplan, H., 2017, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. Klein, P. N. (ed.). Association for Computing Machinery, p. 1479-1496 18 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 0).

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

  Open Access

  • Oracle 100%
  • Query 94%
  • Data structures 78%
  • Stretch 57%
  • Data Structures 32%

• Deterministic partially dynamic single source shortest paths for sparse graphs

  Bernstein, A. & Chechik, S., 2017, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. Klein, P. N. (ed.). Association for Computing Machinery, p. 453-469 17 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 0).

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

  Open Access

  • Sparse Graphs 100%
  • Shortest path 89%
  • Update 61%
  • Black Box 24%
  • Deterministic Algorithm 24%

• Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs

  Chechik, S., Hanseny, T. D., Italiano, G. F., Loitzenbauer, V. & Parotsidis, N., 2017, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. Klein, P. N. (ed.). Association for Computing Machinery, p. 1900-1918 19 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 0).

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

  Open Access

  • Sparse Graphs 100%
  • Directed graphs 98%
  • Fast Algorithm 84%
  • Directed Graph 79%
  • Subgraph 69%

• Fully dynamic all-pairs shortest paths with worst-case update-time revisited

  Abraham, I., Chechik, S. & Krinninger, S., 2017, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. Klein, P. N. (ed.). Association for Computing Machinery, p. 440-452 13 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 0).

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

  Open Access

  • Shortest path 100%
  • Update 92%
  • Directed graphs 36%
  • Deterministic Algorithm 17%
  • Vertex of a graph 17%
• 2016

  Bottleneck paths and trees and deterministic Graphical games

  Chechik, S., Kaplan, H., Thorup, M., Zamir, O. & Zwick, U., 1 Feb 2016, 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016. Vollmer, H. & Ollinger, N. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 27. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 47).

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

  • Directed graphs 100%
  • Random access storage 93%

• Decremental Single-Source Reachability and Strongly Connected Components in Õ(m√n) Total Update Time

  Chechik, S., Hansen, T. D., Italiano, G. F., Lacki, J. & Parotsidis, N., 14 Dec 2016, Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016. IEEE Computer Society, p. 315-324 10 p. 7782945. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2016-December).

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

  • Directed graphs 100%

• Deterministic decremental single source shortest paths: Beyond the O(mn) bound

  Bernstein, A. & Chechik, S., 19 Jun 2016, STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. Mansour, Y. & Wichs, D. (eds.). Association for Computing Machinery, p. 389-397 9 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 19-21-June-2016).

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

  • Set theory 100%

• Near-optimal light spanners

  Chechik, S. & Wulff-Nilsen, C., 2016, 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016. Krauthgamer, R. (ed.). Association for Computing Machinery, p. 883-892 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2).

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

  • Spanners 100%
  • Spanner 86%
  • Stretch 67%
  • Greedy Algorithm 21%
  • Girth 19%

• On dynamic approximate shortest paths for planar graphs with worst-case costs

  Abraham, I., Chechik, S., Delling, D., Goldberg, A. V. & Werneck, R. F., 2016, 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016. Krauthgamer, R. (ed.). Association for Computing Machinery, p. 740-753 14 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2).

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

  Open Access

  • Shortest path 100%
  • Update 92%
  • Planar graph 86%
  • Oracle 74%
  • Query 70%
• 2015

  Approximate distance oracles with improved bounds

  Chechik, S., 14 Jun 2015, STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 1-10 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 14-17-June-2015).

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

  • Data structures 100%

• Approximate nearest neighbor search in metrics of planar graphs

  Abraham, I., Chechik, S., Krauthgamer, R. & Wieder, U., 1 Aug 2015, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015. Garg, N., Jansen, K., Rao, A. & Rolim, J. D. P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 20-42 23 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 40).

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

  • Nearest neighbor search 100%
  • Data structures 15%

• Average distance queries through weighted samples in graphs and metric spaces: High scalability with tight statistical guarantees

  Chechik, S., Cohen, E. & Kaplan, H., 1 Aug 2015, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015. Garg, N., Jansen, K., Rao, A. & Rolim, J. D. P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 659-679 21 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 40).

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

  • Scalability 100%
  • Mean square error 28%
  • Sampling 21%
  • Set theory 19%
• 2014

  Approximate distance oracles with constant query time

  Chechik, S., 2014, STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 654-663 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

  • Data structures 100%

• Better approximation algorithms for the graph diameter

  Chechik, S., Larkin, D. H., Roditty, L., Schoenebeck, G., Tarjan, R. E. & Williams, V. V., 2014, Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Association for Computing Machinery, p. 1041-1052 12 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

  • Approximation algorithms 100%
  • Approximation Algorithms 81%
  • Sparse Graphs 48%
  • Graph in graph theory 42%
  • Approximation 41%

• Distance labels with optimal local stretch

  Abraham, I. & Chechik, S., 2014, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1 ed. Springer Verlag, p. 52-63 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8572 LNCS, no. PART 1).

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

  • Stretch 100%
  • Labeling 81%
  • Labels 70%
  • Oracle 58%
  • Vertex of a graph 23%

• Fully dynamic all-Pairs shortest paths: Breaking the o(n) barrier

  Abraham, I., Chechik, S. & Talwar, K., 1 Sep 2014, Leibniz International Proceedings in Informatics, LIPIcs. Jansen, K., Rolim, J. D. P., Devanur, N. R. & Moore, C. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 1-16 16 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 28).

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

  • Data structures 100%
  • Costs 92%
• 2013

  Compact routing schemes with improved stretch

  Chechik, S., 2013, PODC 2013 - Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing. p. 33-41 9 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

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

• Low-distortion inference of latent similarities from a multiplex social network

  Abraham, I., Chechik, S., Kempe, D. & Slivkins, A., 2013, Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013. Association for Computing Machinery, p. 1853-1872 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

  • Social Networks 100%
  • Electric network analysis 83%
  • Similarity 70%
  • Social Network Analysis 51%
  • Metric 32%

• New additive spanners

  Chechik, S., 2013, Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013. Association for Computing Machinery, p. 498-512 15 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

  • Spanners 100%
  • Spanner 45%
  • Stretch 32%

• Secluded connectivity problems

  Chechik, S., Johnson, M. P., Parter, M. & Peleg, D., 2013, Algorithms, ESA 2013 - 21st Annual European Symposium, Proceedings. p. 301-312 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8125 LNCS).

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

  • Connectivity 100%
  • Polynomials 84%
  • Path 75%
  • NP-hard 71%
  • Steiner Tree 52%
• 2012

  Fault tolerant additive spanners

  Braunschvig, G., Chechik, S. & Peleg, D., 2012, Graph-Theoretic Concepts in Computer Science - 38th International Workshop, WG 2012, Revised Selcted Papers. p. 206-214 9 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7551 LNCS).

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

  • Spanners 100%
  • Fault-tolerant 94%
  • Spanner 63%
  • Stretch 49%
  • Multiplicative 33%

• Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels

  Abraham, I., Chechik, S. & Gavoille, C., 2012, STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing. p. 1199-1217 19 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

  • Labeling 100%
  • Labels 87%

• Improved distance oracles and spanners for vertex-labeled graphs

  Chechik, S., 2012, Algorithms, ESA 2012 - 20th Annual European Symposium, Proceedings. p. 325-336 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7501 LNCS).

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

  • Spanners 100%
  • Oracle 78%
  • Stretch 67%
  • Labels 63%
  • Vertex of a graph 42%

• Multipath Spanners via Fault-Tolerant Spanners

  Chechik, S., Godfroy, Q. & Peleg, D., 2012, Design and Analysis of Algorithms - 1st Mediterranean Conference on Algorithms, MedAlg 2012, Proceedings. Even, G. & Rawitz, D. (eds.). Springer Science and Business Media Deutschland GmbH, p. 108-119 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7659 LNNS).

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

  • Multipath 100%
  • Spanners 87%
  • Fault-tolerant 83%
  • Spanner 58%
  • Stretch 52%

• The fault tolerant capacitated k-center problem

  Chechik, S. & Peleg, D., 2012, Structural Information and Communication Complexity - 19th International Colloquium, SIROCCO 2012, Proceedings. p. 13-24 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7355 LNCS).

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

  • Fault-tolerant 100%
  • Center Problem 98%
  • Polynomials 60%
  • Vertex of a graph 35%
  • Weighted Graph 16%
• 2011

  Fault-tolerant compact routing schemes for general graphs

  Chechik, S., 2011, Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings. PART 2 ed. p. 101-112 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6756 LNCS, no. PART 2).

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

  • Fault-tolerant 100%
  • Routing 86%
  • Graph in graph theory 36%
  • Directly proportional 27%
  • Fault-tolerant Routing 26%
• 2010

  Forbidden-set distance labels for graphs of bounded doubling dimension

  Abraham, I., Chechik, S., Gavoille, C. & Peleg, D., 2010, PODC'10 - Proceedings of the 2010 ACM Symposium on Principles of Distributed Computing. p. 192-200 9 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

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

  • Labels 100%
  • Labeling 86%
  • Polynomials 22%

• f-Sensitivity distance oracles and routing schemes

  Chechik, S., Langberg, M., Peleg, D. & Roditty, L., 2010, Algorithms, ESA 2010 - 18th Annual European Symposium, Proceedings. PART 1 ed. p. 84-96 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6346 LNCS, no. PART 1).

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

  • Routing 100%
  • Oracle 95%
  • Data structures 75%
  • Data Structures 26%
  • Query 25%

• Low-port tree representations

  Chechik, S. & Peleg, D., 2010, Graph-Theoretic Concepts in Computer Science - 35th International Workshop, WG 2009, Revised Papers. p. 66-76 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5911 LNCS).

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

  • Spanning tree 100%
  • Costs 95%
  • Vertex of a graph 92%
  • Trees (mathematics) 46%
  • Labeling 39%

• Rigid and competitive fault tolerance for logical information structures in networks

  Chechik, S. & Peleg, D., 2010, 2010 IEEE 26th Convention of Electrical and Electronics Engineers in Israel, IEEEI 2010. p. 24-25 2 p. 5662210. (2010 IEEE 26th Convention of Electrical and Electronics Engineers in Israel, IEEEI 2010).

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

  • Fault tolerance 100%
  • Flow structure 27%

• Robust fault tolerant uncapacitated facility location

  Chechik, S. & Peleg, D., 2010, STACS 2010 - 27th International Symposium on Theoretical Aspects of Computer Science. p. 191-202 12 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 5).

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

  • Costs 100%
  • NP-hard 50%
  • Polynomials 40%