Paper Info
Title
Maintenance of Triconnected Components of Graphs (Extended Abstract)
Abstract
In this paper, optimal algorithms and data structures are presented to maintain the triconnected components of a general graph, under insertions of edges in the graph. At any moment, the data structure can answer the following type of query: given two nodes in the graph, are these nodes triconnected. Starting from an empty graph of n nodes (i.e., a graph with no edges) the solution runs in O(n + m.(m, n)) total time, where m is the total number of queries and edge insertions. The solution allows for insertions of nodes also.
Year
DOI
Venue
1992
10.1007/3-540-55719-9_87
ICALP
Keywords
Field
DocType
triconnected components,extended abstract,data structure
Graph,Discrete mathematics,Combinatorics,Computer science,SPQR tree
Conference
ISBN
Citations 
PageRank 
3-540-55719-9
8
0.60
References 
Authors
13
1
Name
Order
Citations
PageRank
Johannes A. La Poutré130824.78