Paper Info
Title
Arboricity, h-index, and dynamic algorithms
Abstract
We propose a new data structure for manipulating graphs, called h-graph, which is particularly suited for designing dynamic algorithms. The structure itself is simple, consisting basically of a triple of elements, for each vertex of the graph. The overall size of all triples is O(n+m), for a graph with n vertices and m edges. We describe algorithms for performing the basic operations related to dynamic applications, as insertions and deletions of vertices or edges, and adjacency queries. The data structure employs a technique first described by Chiba and Nishizeki [Chiba, Nishizeki, Arboricity and subgraph listing algorithms, SIAM J. Comput. 14 (1) (1985) 210-223], and relies on the arboricity of graphs. Using the proposed data structure, we describe 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. These algorithms are the first of their kind to be proposed in the literature. In fact, the dynamic algorithms for the above problems lead directly to new static algorithms, and using the data structure we also design new static algorithms for the problems of counting subgraphs of size 4, recognizing cop-win graphs and recognizing strongly chordal graphs. The complexities of all of the proposed static algorithms improve over the complexities of the so far existing algorithms, for graphs of low arboricity. In addition, for the problems of counting subgraphs of size 4 and recognizing diamond-free graphs, the improvement is general.
Year
DOI
Venue
2010
10.1016/j.tcs.2011.12.006
Theor. Comput. Sci.
Keywords
DocType
Volume
h,data structures,arboricity
Journal
426-427,
ISSN
Citations 
PageRank 
0304-3975
17
0.85
References 
Authors
16
3
Name
Order
Citations
PageRank
Min Chih Lin125921.22
Francisco J. Soulignac210110.56
Jayme L. Szwarcfiter354645.97