38 citations · 45 across the 8 of their papers we have counts for
10 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…
Conditionally Optimal Algorithms for Generalized Büchi Games
Krishnendu Chatterjee, Wolfgang Dvořák, Monika Henzinger +1
Games on graphs provide the appropriate framework to study several central problems in computer science, such as the verification and synthesis of reactive systems. One of the most…
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…
Model and Objective Separation with Conditional Lower Bounds: Disjunction is Harder than Conjunction
Krishnendu Chatterjee, Wolfgang Dvořák, Monika Henzinger +1
Given a model of a system and an objective, the model-checking question asks whether the model satisfies the objective. We study polynomial-time problems in two classical models, g…
Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time
Monika Henzinger, Sebastian Krinninger, Veronika Loitzenbauer
We present faster algorithms for computing the 2-edge and 2-vertex strongly connected components of a directed graph, which are straightforward generalizations of strongly connecte…
Improved Algorithms for Parity and Streett objectives
Krishnendu Chatterjee, Monika Henzinger, Veronika Loitzenbauer
The computation of the winning set for parity objectives and for Streett objectives in graphs as well as in game graphs are central problems in computer-aided verification, with ap…
Approximating the minimum cycle mean
Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger +1
We consider directed graphs where each edge is labeled with an integer weight and study the fundamental algorithmic question of computing the value of a cycle with minimum mean wei…