Arboricity, h-Index, and Dynamic Algorithms

Details Arboricity, h-Index, and Dynamic Algorithms Arboricity, h-Index, and Dynamic Algorithms

2010-05-12

arxiv.org/abs/1005.2211v1

Computer Science

Data Structures and Algorithms

19 pages, no figures

Scientific paper

10.1016/j.tcs.2011.12.006

In this paper we present a modification of a technique by Chiba and Nishizeki [Chiba and Nishizeki: Arboricity and Subgraph Listing Algorithms, SIAM J. Comput. 14(1), pp. 210--223 (1985)]. Based on it, we design a data structure suitable for dynamic graph algorithms. We employ the data structure to formulate new algorithms for several problems, including counting subgraphs of four vertices, recognition of diamond-free graphs, cop-win graphs and strongly chordal graphs, among others. We improve the time complexity for graphs with low arboricity or h-index.

Affiliated with

Also associated with

No associations

Rating

Arboricity, h-Index, and Dynamic Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Arboricity, h-Index, and Dynamic Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arboricity, h-Index, and Dynamic Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-640060