Joan Feigenbaum, Sampath Kannan  Home/Search
Context Related
| att.com/~jf/pubs/dcmhandbook.ps Cached: PS.gz PS PDF DjVu Image Update Help From: cryptosoft.com/html/secpub (more) Homepages: J.Feigenbaum S.Kannan HPSearch (Update Links) |
Rate this article:      (best)Comment on this article |
Abstract: INTRODUCTION Dynamic graph algorithms are algorithms that maintain properties of a (possibly edgeweighted) graph while the graph is changing. These algorithms are potentially useful in a number of application areas, including communication networks, VLSI design, distributed computing, and graphics, where the underlying graphs are subject to dynamic changes. Efficient dynamic graph algorithms are also used as subroutines in algorithms that build and modify graphs as part of larger tasks, e.g.,... (Update)
Context of citations to this paper: More
...graph problems on undirected graphs has met with much success, for a number of graph properties. For a survey of the earlier work, see [6]. For more recent work, see [10, 8, 9] Directed graph problems have proven to be much tougher and very little is known, especially...
...graph problems on undirected graphs has met with much success, for a number of graph properties. For a survey of the earlier work, see [5]. For more recent work, see [8, 7, 9] Directed graph problems have proven to be much tougher and very little is known, especially for fully...
Cited by: More
A Fully Dynamic Algorithm for Maintaining the Transitive Closure - King, Sagert (1999) (Correct)
Active bibliography (related documents): More All
0.7: Data Structures for Maintaining Biconnectivity and 2-edge.. - Mendel (1994) (Correct)
0.6: Lower Bounds for Fully Dynamic Connectivity Problems in Graphs - Fredman, Henzinger (Correct)
0.3: Separator-Based Sparsification II: Edge And Vertex.. - Eppstein, Galil.. (1998) (Correct)
Similar documents based on text: More All
0.5: Alcom-FT Technical Report Series - Alcomft-Tr- Revised November (Correct)
0.1: Lower Bounds on Random-Self-Reducibility (Extended Abstract) - Feigenbaum, al. (1990) (Correct)
0.1: An Approximate L¹-Difference Algorithm for Massive.. - Feigenbaum, Kannan, al. (2001) (Correct)
Related documents from co-citation: More All
2: Size-estimation framework with applications to transitive closure and reachabili.. (context) - Cohen
2: Maintenance of transitive closure and transitive reduction of graphs - Poutr'e, van Leeuwen - 1988
2: The Design and Analysis of Algorithms (context) - Kozen - 1992
BibTeX entry: (Update)
J. Feigenbaum and S. Kannan, "Dynamic Graph Algorithms", in Handbook of Discrete and Combinatorial Mathematics, pp. 583-591. http://citeseer.nj.nec.com/feigenbaum00dynamic.html More
@incollection{ feigenbaum00dynamic,
author = "Feigenbaum and Kannan",
title = "Dynamic Graph Algorithms",
booktitle = "Handbook of Discrete and Combinatorial Mathematics, {CRC} Press, 2000",
editor = "Rosen and Michaels and Gross and Grossman and Shier",
year = "2000",
url = "citeseer.nj.nec.com/feigenbaum00dynamic.html" }
Citations (may not include all citations):223 Primitives for the Manipulation of General Subdivisions and .. (context) - Guibas, Stolfi - 1985
155 A Data Structure for Dynamic Trees (context) - Sleator, Tarjan - 1983
104 Data Structures for On-Line Updating of Minimum Spanning Tre.. (context) - Frederickson - 1985
94 Sparsification -- A Technique for Speeding up Dynamic Graph .. (context) - Eppstein, Galil et al. - 1992
67 Efficiency of a Good but not Linear Set Union Algorithm (context) - Tarjan - 1975
52 Ambivalent Data Structures for Dynamic 2-Edge-Connectivity a.. - Frederickson - 1991
51 Linear Time Algorithms for Finding a Sparse k- connected Spa.. (context) - Nagamochi, Ibaraki - 1992
44 Maintenance of a Minimum Spanning Forest in a Dynamic Plane .. - Eppstein, Italiano et al. - 1992
39 Maintaining Bridge-Connected and Biconnected Components On-L.. (context) - Westbrook, Tarjan - 1992
37 Incremental Algorithms for Minimal Length Paths (context) - Ausiello, Italiano et al. - 1991
34 Faster Shortest-Path Algorithms for Planar Graphs - Klein, Rao et al. - 1994
31 Improved Data Structures for Fully Dynamic Biconnectivity (context) - Rauch - 1994
25 Updating Distances in Dynamic Graphs (context) - Even, Gazit - 1985
25 Separator Based Sparsification for Dynamic Planar Graph Algo.. (context) - Eppstein, Galil et al. - 1993
19 Department of Information and Computer Science (context) - Eppstein, Galil et al. - 1993
17 Randomized Dynamic Algorithms with Polylogarithmic Time Per .. (context) - Henzinger, King - 1995
15 Scan-First Search and Sparse Certificates: An Improved Paral.. (context) - Cheriyan, Kao et al. - 1993
13 A Dynamization of the All-Pairs Least-Cost Path Problem (context) - Rohnert - 1985
12 Average Case Analysis of Dynamic Graph Algorithms - Alberts, Henzinger - 1995
9 Techniques for the Design of Parallel Graph Algorithms (context) - Thurimella - 1989
9 Incremental Algorithms for the Single-Source Shortest Path P.. (context) - Frigioni, Marchetti-Spaccamela et al. - 1994
6 Reducing Edge Connectivity to Vertex Connectivity (context) - Galil, Italiano - 1991
5 Fully Dynamic Graph Algorithms and Their Data Structures (context) - Rauch - 1993
2 Fully Dynamic Planarity Testing in Embedded Graphs (context) - Italiano, Poutr'e et al. - 1993
2 Fully Dynamic 2-Edge-Connectivity in Planar Graphs (context) - Hershberger, Rauch et al. - 1994
1 Lower Bounds for Dynamic Connectivity Problems in Graphs (context) - Fredman, Rauch
Documents on the same site (http://www.cryptosoft.com/html/secpub.htm): More
A new approach for delegation using hierarchical delegation.. - Ding, Petersen (1995) (Correct)
A Uniform-Complexity Treatment of Encryption and Zero-Knowledge - Goldreich (1991) (Correct)
On signature schemes with threshold verification detecting.. - Petersen, Michels (1997) (Correct)
Online articles have much greater impact More about CiteSeer Add search form to your site Submit documents Feedback
CiteSeer - citeseer.org - Terms of Service - Privacy Policy - Copyright © 1997-2002 NEC Research Institute