0000000000114744

AUTHOR

Giuseppe F. Italiano

showing 3 related works from this author

Dynamic 2- and 3-connectivity on planar graphs

1992

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 of O(n log n) time under any sequence of at most O(n) deletions. This gives O(log n) amortized time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total of O(n log2n) time. This gives O(log2n) amortized time per deletion. The space required by all our data structures is O(n).

Amortized analysisBook embeddingPlanar straight-line graph1-planar graphPlanar graphCombinatoricssymbols.namesakePathwidthChordal graphTheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITYOuterplanar graphData_FILESsymbolsMathematicsofComputing_DISCRETEMATHEMATICSMathematics
researchProduct

Maintaining Dynamic Minimum Spanning Trees: An Experimental Study

2010

AbstractWe report our findings on an extensive empirical study on the performance of several algorithms for maintaining minimum spanning trees in dynamic graphs. In particular, we have implemented and tested several variants of the polylogarithmic algorithm by Holm et al., sparsification on top of Frederickson’s algorithm, and other (less sophisticated) dynamic algorithms. In our experiments, we considered as test sets several random, semi-random and worst-case inputs previously considered in the literature together with inputs arising from real-world applications (e.g., a graph of the Internet Autonomous Systems).

Random graphSpanning treeExperimental analysisMinimum spanning tree algorithmsbusiness.industryApplied MathematicsExperimental analysis; Minimum spanning tree algorithms; Dynamic graphsMinimum spanning treeGraphDistributed minimum spanning treedynamic graphs; experimental analysis; minimum spanning tree algorithmsEmpirical researchDynamic problemDiscrete Mathematics and CombinatoricsThe InternetbusinessSettore ING-INF/05 - Sistemi di Elaborazione delle InformazioniAlgorithmMathematicsDynamic graphs
researchProduct

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