5 papers
Symbolic Algorithms for Graphs and Markov Decision Processes with Fairness Objectives
Krishnendu Chatterjee, Monika Henzinger, Veronika Loitzenbauer +2
Given a model and a specification, the fundamental model-checking problem asks for algorithmic verification of whether the model satisfies the specification. We consider graphs and…
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…
Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs
Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano +2
Connectivity related concepts are of fundamental interest in graph theory. The area has received extensive attention over four decades, but many problems remain unsolved, especiall…
Ad Exchange: Envy-Free Auctions with Mediators
Oren Ben-Zwi, Monika Henzinger, Veronika Loitzenbauer
Ad exchanges are an emerging platform for trading advertisement slots on the web with billions of dollars revenue per year. Every time a user visits a web page, the publisher of th…