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
13 papers · 2 filters
Feasibility Tests for Recurrent Real-Time Tasks in the Sporadic DAG Model
Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, Sebastian Stiller +1
A model has been proposed in [Baruah et al., in Proceedings of the IEEE Real-Time Systems Symposium 2012] for representing recurrent precedence-constrained tasks to be executed on…
A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market
Ran Duan, Kurt Mehlhorn
We present the first combinatorial polynomial time algorithm for computing the equilibrium of the Arrow-Debreu market model with linear utilities.
The Cost of Address Translation
Tomasz Jurkiewicz, Kurt Mehlhorn
Modern computers are not random access machines (RAMs). They have a memory hierarchy, multiple cores, and virtual memory. In this paper, we address the computational cost of addres…
Fast Hamiltonicity checking via bases of perfect matchings
Marek Cygan, Stefan Kratsch, Jesper Nederlof
For an even integer t \geq 2, the Matchings Connecivity matrix H_t is a matrix that has rows and columns both labeled by all perfect matchings of the complete graph K_t on t vertic…
Certifying 3-Edge-Connectivity
Kurt Mehlhorn, Adrian Neumann, Jens M. Schmidt
We present a certifying algorithm that tests graphs for 3-edge-connectivity; the algorithm works in linear time. If the input graph is not 3-edge-connected, the algorithm returns a…
Black-Box Complexity: Breaking the Barrier of LeadingOnes
Benjamin Doerr, Carola Winzen
We show that the unrestricted black-box complexity of the -dimensional XOR- and permutation-invariant LeadingOnes function class is . This shows tha…