2.8k citations
- Max Planck SocietyDE261 papers
- Saarland UniversityDE124 papers
- Technische Universität BerlinDE55 papers
- Centre National de la Recherche ScientifiqueFR41 papers
- Korea UniversityKR41 papers
- Stanford UniversityUS25 papers
- Institut national de recherche en sciences et technologies du numériqueFR24 papers
- ETH ZurichCH21 papers
- Helmholtz Center for Information SecurityDE20 papers
- Technical University of MunichDE20 papers
- Université de LorraineFR17 papers
- University of LuxembourgLU16 papers
9 papers · 1 filter
Continuous Monitoring of Distributed Data Streams over a Time-based Sliding Window
Ho-Leung Chan, Tak-Wah Lam, Lap-Kei Lee +1
The past decade has witnessed many interesting algorithms for maintaining statistics over a data stream. This paper initiates a theoretical study of algorithms for monitoring distr…
Probabilistic one-player Ramsey games via deterministic two-player games
Michael Belfrage, Torsten Mütze, Reto Spöhel
Consider the following probabilistic one-player game: The board is a graph with vertices, which initially contains no edges. In each step, a new edge is drawn uniformly at rand…
Preprocessing of Min Ones Problems: A Dichotomy
Stefan Kratsch, Magnus Wahlstrom
A parameterized problem consists of a classical problem and an additional component, the so-called parameter. This point of view allows a formal definition of preprocessing: Given…
Generating Concise and Readable Summaries of XML Documents
Maya Ramanath, Kondreddi Sarath Kumar, Georgiana Ifrim
XML has become the de-facto standard for data representation and exchange, resulting in large scale repositories and warehouses of XML data. In order for users to understand and ex…
3-Connected Cores In Random Planar Graphs
Nikolaos Fountoulakis, Konstantinos Panagiotou
The study of the structural properties of large random planar graphs has become in recent years a field of intense research in computer science and discrete mathematics. Nowadays,…
Improved approximation guarantees for weighted matching in the semi-streaming model
Leah Epstein, Asaf Levin, Julian Mestre +1
We study the maximum weight matching problem in the semi-streaming model, and improve on the currently best one-pass algorithm due to Zelke (Proc. of STACS2008, pages 669-680) by d…