Search results for "Amortized analysis"

showing 1 items of 11 documents

Decremental 2- and 3-connectivity on planar graphs

1996

We study the problem of maintaining the 2-edge-, 2-vertex-, and 3-edge-connected components of a dynamic planar graph subject to edge deletions. The 2-edge-connected components can be maintained in a total ofO(n logn) time under any sequence of at mostO(n) deletions. This givesO(logn) amortized time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total ofO(n log2n) time. This givesO(log2n) amortized time per deletion. The space required by all our data structures isO(n). All our time bounds improve previous bounds.

Vertex (graph theory)Discrete mathematicsDynamic data structuresAmortized analysisGeneral Computer ScienceApplied MathematicsVertex connectivityPlanar graphsData structureEdge connectivityComputer Science ApplicationsPlanar graphCombinatoricssymbols.namesakeAnalysis of algorithms Dynamic data structures Edge connectivity Planar graphs Vertex connectivitysymbolsAnalysis of algorithmsVertex connectivityDynamic data structuresAnalysis of algorithmsMathematicsAlgorithmica
researchProduct