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
14 papers · 1 filter
The Violation Heap: A Relaxed Fibonacci-Like Heap
Amr Elmasry
We give a priority queue that achieves the same amortized bounds as Fibonacci heaps. Namely, find-min requires O(1) worst-case time, insert, meld and decrease-key require O(1) amor…
Approximating the least hypervolume contributor: NP-hard in general, but fast in practice
Karl Bringmann, Tobias Friedrich
The hypervolume indicator is an increasingly popular set measure to compare the quality of two Pareto sets. The basic ingredient of most hypervolume indicator based optimization al…
On combinations of local theory extensions
Viorica Sofronie-Stokkermans
In this paper we study possibilities of efficient reasoning in combinations of theories over possibly non-disjoint signatures. We first present a class of theory extensions (called…
Superposition for Fixed Domains
Matthias Horbach, Christoph Weidenbach
Superposition is an established decision procedure for a variety of first-order logic theories represented by sets of clauses. A satisfiable theory, saturated by superposition, imp…
Approximating the volume of unions and intersections of high-dimensional geometric objects
Karl Bringmann, Tobias Friedrich
We consider the computation of the volume of the union of high-dimensional geometric objects. While showing that this problem is #P-hard already for very simple bodies (i.e., axis-…
The t-stability number of a random graph
Nikolaos Fountoulakis, Ross J. Kang, Colin McDiarmid
Given a graph G = (V,E), a vertex subset S is called t-stable (or t-dependent) if the subgraph G[S] induced on S has maximum degree at most t. The t-stability number of G is the ma…