3 citations · 5 across the 5 of their papers we have counts for
4 papers · 1 filter
Algorithms and Conditional Lower Bounds for Planning Problems
Krishnendu Chatterjee, Wolfgang Dvořák, Monika Henzinger +1
We consider planning problems for graphs, Markov decision processes (MDPs), and games on graphs. While graphs represent the most basic planning model, MDPs represent interaction wi…
Lower Bounds for Symbolic Computation on Graphs: Strongly Connected Components, Liveness, Safety, and Diameter
Krishnendu Chatterjee, Wolfgang Dvořák, Monika Henzinger +1
A model of computation that is widely used in the formal analysis of reactive systems is symbolic algorithms. In this model the access to the input graph is restricted to consist o…
Improved Set-based Symbolic Algorithms for Parity Games
Krishnendu Chatterjee, Wolfgang Dvořák, Monika Henzinger +1
Graph games with ω-regular winning conditions provide a mathematical framework to analyze a wide range of problems in the analysis of reactive systems and programs (such as the syn…
Online Ad Assignment with an Ad Exchange
Wolfgang Dvořák, Monika Henzinger
Ad exchanges are becoming an increasingly popular way to sell advertisement slots on the internet. An ad exchange is basically a spot market for ad impressions. A publisher who has…