Arboricity, h-index, and dynamic algorithms
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 w...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Artículo publishedVersion |
| Publicado: |
2012
|
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_03043975_v426-427_n_p75_Lin https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_03043975_v426-427_n_p75_Lin_oai |
| Aporte de: |
| id |
I28-R145-paper_03043975_v426-427_n_p75_Lin_oai |
|---|---|
| record_format |
dspace |
| spelling |
I28-R145-paper_03043975_v426-427_n_p75_Lin_oai2024-08-16 Lin, M.C. Soulignac, F.J. Szwarcfiter, J.L. 2012 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. Fil:Lin, M.C. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Soulignac, F.J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf http://hdl.handle.net/20.500.12110/paper_03043975_v426-427_n_p75_Lin info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar Theor Comput Sci 2012;426-427:75-90 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 Arboricity, h-index, and dynamic algorithms info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_03043975_v426-427_n_p75_Lin_oai |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-145 |
| collection |
Repositorio Digital de la Universidad de Buenos Aires (UBA) |
| topic |
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 |
| spellingShingle |
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 Lin, M.C. Soulignac, F.J. Szwarcfiter, J.L. Arboricity, h-index, and dynamic algorithms |
| topic_facet |
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 |
| description |
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. |
| format |
Artículo Artículo publishedVersion |
| author |
Lin, M.C. Soulignac, F.J. Szwarcfiter, J.L. |
| author_facet |
Lin, M.C. Soulignac, F.J. Szwarcfiter, J.L. |
| author_sort |
Lin, M.C. |
| title |
Arboricity, h-index, and dynamic algorithms |
| title_short |
Arboricity, h-index, and dynamic algorithms |
| title_full |
Arboricity, h-index, and dynamic algorithms |
| title_fullStr |
Arboricity, h-index, and dynamic algorithms |
| title_full_unstemmed |
Arboricity, h-index, and dynamic algorithms |
| title_sort |
arboricity, h-index, and dynamic algorithms |
| publishDate |
2012 |
| url |
http://hdl.handle.net/20.500.12110/paper_03043975_v426-427_n_p75_Lin https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_03043975_v426-427_n_p75_Lin_oai |
| work_keys_str_mv |
AT linmc arboricityhindexanddynamicalgorithms AT soulignacfj arboricityhindexanddynamicalgorithms AT szwarcfiterjl arboricityhindexanddynamicalgorithms |
| _version_ |
1809356816037969920 |