University of Haifa

output

19922026

most citedThe new world atlas of artificial night sky brightness

1.7k citations

Showing cs.DSShow all

36 papers · 1 filter

cs.DS2025

Approximate Cartesian Tree Matching with One Difference

Bastien Auvray, Julien David, Samah Ghazawi +3

Cartesian tree pattern matching consists of finding all the factors of a text that have the same Cartesian tree than a given pattern. There already exist theoretical and practical…

cs.DS2024

Massively Parallel Algorithms for Approximate Shortest Paths

Michal Dory, Shaked Matar

We present fast algorithms for approximate shortest paths in the massively parallel computation (MPC) model. We provide randomized algorithms that take $p o l y (lo g lo g n)$ rounds…

cs.DS2021

Strongly Sublinear Algorithms for Testing Pattern Freeness

Ilan Newman, Nithin Varma

For a permutation $π : [k] \to [k]$ , a function $f : [n] \to R$ contains a $π$ -appearance if there exists $1 \leq i_{1} < i_{2} < \dots < i_{k} \leq n$ such that for all $s,t \in [k…

cs.DS2020

A $2^{O (k)} n$ algorithm for $k$ -cycle in minor-closed graph families

Raphael Yuster

Let $C$ be a proper minor-closed family of graphs. We present a randomized algorithm that given a graph $G \in C$ with $n$ vertices, finds a simple cycle of s…

cs.DS2020★ 6 cited

Streaming Submodular Maximization under a $k$ -Set System Constraint

Ran Haba, Ehsan Kazemi, Moran Feldman +1

In this paper, we propose a novel framework that converts streaming algorithms for monotone submodular maximization into streaming algorithms for non-monotone submodular maximizati…

cs.DS2019★ 7 cited

Cartesian Tree Matching and Indexing

Sung Gwan Park, Amihood Amir, Gad M. Landau +1

We introduce a new metric of match, called Cartesian tree matching, which means that two strings match if they have the same Cartesian trees. Based on Cartesian tree matching, we d…