Arboricity, h-Index and Graph Algorithms.

MIN CHIH LIN; FRANCISCO J. SOULIGNAC; JAYME L. SZWARCFITER

Workshop; Workshop Brazil - Cornell; 2012

We propose a new data structure for manipulating graphs, which is particularly suited for designing dynamic algorithms. We describe the basic operations related to dynamic applications, as insertions and deletions of vertices or edges, and adjacency queries. Using the proposed tool, we develop several dynamic algorithms for solving problems as listing the cliques of a given size, recognizing diamond- free graphs, and finding simple, simplicial and dominated vertices. On the other hand, using the data struicture we also describe new static algorithms for the problems of counting subgraphs of size 4, recognizing cop-win graphs and recognizing strongly chordal graphs. Most of the above dynamic algorithms are the first of their kind in the literature, while the static algorithms improve in some aspect over existing methods.