Navegar

Colección

Datos Estadísticas

Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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) 210223], 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. © 2011 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:Arboricity, h-index, and dynamic algorithms
Autor:Lin, M.C.; Soulignac, F.J.; Szwarcfiter, J.L.
Filiación:CONICET and Universidad de Buenos Aires, Facultad de Ciencias Exactas y Naturales, Departamento de Computación, Buenos Aires, Argentina
Universidad de Buenos Aires, Facultad de Ciencias Exactas y Naturales, Departamento de Computación, Buenos Aires, Argentina
Universidade Federal Do Rio de Janeiro, Instituto de Matemática, NCE and COPPE, Caixa Postal 2324, 20001-970 Rio de Janeiro, RJ, Brazil
Palabras clave:Arboricity; Cop-win graphs; Data structures; Diamond-free graphs; Dynamic algorithms; h-index; Strongly chordal graphs; Arboricity; Cop-win graphs; Diamond-free graphs; Dynamic algorithms; H indices; Strongly chordal graph; Algorithms; Data structures; Diamonds; Graphic methods; Indexing (of information); Problem solving; Graph theory
Año:2012
Volumen:426-427
Página de inicio:75
Página de fin:90
DOI: http://dx.doi.org/10.1016/j.tcs.2011.12.006
Título revista:Theoretical Computer Science
Título revista abreviado:Theor Comput Sci
ISSN:03043975
CODEN:TCSCD
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_03043975_v426-427_n_p75_Lin.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v426-427_n_p75_Lin

Referencias:

  • Alon, N., Yuster, R., Zwick, U., Finding and Counting Given Length Cycles (1997) Algorithmica (New York), 17 (3), pp. 209-223
  • Bandelt, H.-J., Prisner, E., Clique graphs and Helly graphs (1991) J. Combin. Theory Ser. B, 51 (1), pp. 34-45
  • Bollobs, B., (2004) Extremal Graph Theory, , Dover Publications Inc Mineola, NY (reprint of the 1978 original)
  • Chiba, N., Nishizeki, T., Arboricity and subgraph listing algorithms (1985) SIAM J. Comput., 14 (1), pp. 210-223
  • Conforti, M., ( K 4 - e) -free perfect graphs and star cutsets (1989) Combinatorial Optimization, 1403 VOL., pp. 236-253. , B. Simeone, Como, 1986 Lecture Notes in Math. Springer Berlin
  • Coppersmith, D., Winograd, S., Matrix multiplication via arithmetic progressions (1990) J. Symbolic Comput., 9 (3), pp. 251-280
  • Eisenbrand, F., Grandoni, F., On the complexity of fixed parameter clique and dominating set (2004) Theoret. Comput. Sci., 326 (13), pp. 57-67
  • Eppstein, D., Spiro, E.S., The h-index of a graph and its application to dynamic subgraph statistics (2009) Algorithms and Data Structures, 5664 VOL., pp. 278-289. , F.K.H.A. Dehne, M.L. Gavrilova, J.-R. Sack, C.D. Tth, 11th International Symposium, WADS 2009, Banff, Canada, August 2123, 2009. Proceedings Lecture Notes in Computer Science Springer
  • Farber, M., Characterizations of strongly chordal graphs (1983) Discrete Math., 43 (23), pp. 173-189. , http://dx.doi.org/10.1016/0012-365X(83)90154-1, 10.1016/0012-365X(83)90154-1 URL
  • Fonlupt, J., Zemirline, A., A polynomial recognition algorithm for perfect K 4 \\ e -free graphs (1993) Rev. Maghrbine Math., 2 (1), pp. 1-26
  • Kloks, T., Kratsch, D., Mller, H., Finding and counting small induced subgraphs efficiently (2000) Inform. Process. Lett., 74 (34), pp. 115-121
  • Mahadev, N.-V.R., Wang, T.M., On uniquely intersectable graphs (1999) Discrete Math., 207, pp. 149-159
  • Nowakowski, R., Winkler, P., Vertex-to-vertex pursuit in a graph (1983) Discrete Math., 43 (23), pp. 235-239
  • Paige, R., Tarjan, R.E., Three partition refinement algorithms (1987) SIAM J. Computing, 16 (6), pp. 973-989
  • Poston, T., (1971) Fuzzy Geometry, , Ph.D. Thesis, University of Warwick
  • Quilliot, A., (1983) Homomorphismes, Points Fixes, Rtractions et Jeux de Poursuite dans les Graphes, les Ensembles Ordonns et les Espaces Mtriques, , Ph.D. Thesis, Universit de Paris VI, France
  • Spinrad, J.P., Doubly lexical ordering of dense 0-1 matrices (1993) Inform. Process. Lett., 45, pp. 229-235
  • Spinrad, J.P., Efficient graph representations (2003) Fields Institute Monographs, 19. , American Mathematical Society Providence, RI
  • Spinrad, J.P., Recognizing quasi-triangulated graphs (2004) Discrete Appl. Math., 138 (12), pp. 203-213
  • Szwarcfiter, J.L., A survey on clique graphs (2003) Recent Advances in Algorithms and Combinatorics, 11, pp. 109-136. , C. Linhares Sales, B. Reed, CMS Books Math./Ouvrages Math. SMC Springer New York
  • Talmaciu, M., Nechita, E., Recognition algorithm for diamond-free graphs (2007) Informatica (Vilnius), 18 (3), pp. 457-462
  • Tucker, A., Coloring perfect ( K 4 - e) -free graphs (1987) J. Combin. Theory Ser. B, 42 (3), pp. 313-318
  • Vassilevska, V., (2008) Efficient Algorithms for Path Problems in Weighted Graphs, , Ph.D. Thesis, School of Computer Science, Carnegie Mellon University, August

Citas:

---------- APA ----------
Lin, M.C., Soulignac, F.J. & Szwarcfiter, J.L. (2012) . Arboricity, h-index, and dynamic algorithms. Theoretical Computer Science, 426-427, 75-90.
http://dx.doi.org/10.1016/j.tcs.2011.12.006
---------- CHICAGO ----------
Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L. "Arboricity, h-index, and dynamic algorithms" . Theoretical Computer Science 426-427 (2012) : 75-90.
http://dx.doi.org/10.1016/j.tcs.2011.12.006
---------- MLA ----------
Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L. "Arboricity, h-index, and dynamic algorithms" . Theoretical Computer Science, vol. 426-427, 2012, pp. 75-90.
http://dx.doi.org/10.1016/j.tcs.2011.12.006
---------- VANCOUVER ----------
Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L. Arboricity, h-index, and dynamic algorithms. Theor Comput Sci. 2012;426-427:75-90.
http://dx.doi.org/10.1016/j.tcs.2011.12.006