Personne

Monika Henzinger

Cette personne n’est plus à l’EPFL

Publications associées (53)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

Lower bounds for fully dynamic connectivity problems in graphs

Monika Henzinger

We prove lower bounds on the complexity of maintaining fully dynamic k-edge or k-vertex connectivity in plane graphs and in (k - 1)-vertex connected graphs. We show an amortized lower bound of 0(log n/k(log log n + log b)) per edge insertion, deletion, o ...

1998

Sampling to provide or to bound: With applications to fully dynamic graph algorithms

Monika Henzinger

In dynamic graph algorithms the following provide-or-bound problem has to be solved quickly: Given a set S containing a subset R and a way of generating random elements from S testing for membership in R, either (i) provide an element of R, or (ii) give a ...

1997

Exploring unknown environments

Monika Henzinger

We consider exploration problems where a robot has to construct a complete map of an unknown environment. We assume that the environment is modeled by a directed, strongly connected graph. The robot's task is to visit all nodes and edges of the graph using ...

ACM1997

A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity

Monika Henzinger

This paper presents insertions-only algorithms for maintaining the exact and/or approximate size of the minimum edge cut and the minimum vertex cut of a graph. The algorithms output the approximate or exact size k in time O(1) and a cut of size K in time l ...

1997

Faster Shortest-Path Algorithms for Planar Graphs

Monika Henzinger

We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph with the source and sink on the same face. For the case wh ...

1997

Continuous Profiling: Where Have All the Cycles Gone?

Monika Henzinger

This article describes the Digital Continuous Profiling Infrastructure, a sampling-based profiling system designed to run continuously on production systems. The system supports multiprocessors, works on unmodified executables, and collects profiles for en ...

1997

On the number of small cuts in a graph

Monika Henzinger

We prove that in an undirected graph there are at most O(n2) cuts of size strictly less than 3/2 of the size of the minimum cut. ...

1996

Computing vertex connectivity: New bounds from old techniques

Monika Henzinger

The vertex connectivity K of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the vertex connectivity and a corresponding separator. The time ...

IEEE1996

Fully dynamic biconnectivity and transitive closure

Monika Henzinger

This paper presents an algorithm for the fully dynamic biconnectivity problem whose running time is exponentially faster than all previously known solutions. It is the first dynamic algorithm that answers biconnectivity queries in time O(pow2(log(n)) in a ...

1995

Fully dynamic biconnectivity and transitive closure

Monika Henzinger

IEEE1995