id: 06039145
dt: j
an: 06039145
au: Lin, Min Chih; Soulignac, Francisco J.; Szwarcfiter, Jayme L.
ti: Arboricity, $h$-index, and dynamic algorithms.
so: Theor. Comput. Sci. 426-427, 75-90 (2012).
py: 2012
pu: Elsevier Science Publishers, Amsterdam
la: EN
cc: 
ut: arboricity; cop-win graphs; data structures; diamond-free graphs; dynamic
    algorithms; $h$-index; strongly chordal graphs
ci: Zbl 0572.68053
li: doi:10.1016/j.tcs.2011.12.006
ab: Summary: 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 {\it N. Chiba} and {\it T. Nishizeki} [SIAM J. Comput. 14,
    210‒223 (1985; Zbl 0572.68053)], 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.
rv: