Arboricity, h-index, and dynamic algorithms

Mostrar todas las versiones(3)

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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L.
Formato: JOUR
Materias:
Arboricity
Cop-win graphs
Data structures
Diamond-free graphs
Dynamic algorithms
h-index
Strongly chordal graphs
H indices
Strongly chordal graph
Algorithms
Diamonds
Graphic methods
Indexing (of information)
Problem solving
Graph theory
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03043975_v426-427_n_p75_Lin
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_03043975_v426-427_n_p75_Lin
record_format dspace
spelling todo:paper_03043975_v426-427_n_p75_Lin2023-10-03T15:20:26Z Arboricity, h-index, and dynamic algorithms Lin, M.C. Soulignac, F.J. Szwarcfiter, J.L. 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 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_03043975_v426-427_n_p75_Lin
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (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 JOUR
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
url http://hdl.handle.net/20.500.12110/paper_03043975_v426-427_n_p75_Lin
work_keys_str_mv AT linmc arboricityhindexanddynamicalgorithms
AT soulignacfj arboricityhindexanddynamicalgorithms
AT szwarcfiterjl arboricityhindexanddynamicalgorithms
_version_ 1807315015711064064

Ejemplares similares