Arboricity, h-index, and dynamic algorithms

DOI10.1016/J.TCS.2011.12.006zbMATH Open1243.68228OpenAlexW1904294951MaRDI QIDQ418737FDOQ418737

Authors: Min Chih Lin, Francisco J. Soulignac, Jayme L. Szwarcfiter 

Publication date: 30 May 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.12.006

Recommendations

• Fully dynamic arboricity maintenance
• Fully dynamic arboricity maintenance
• Adjacency queries in dynamic sparse graphs
• A dynamic data structure for counting subgraphs in sparse graphs
• Fully dynamic algorithms for chordal graphs and split graphs

zbMATH Keywords

data structuresarboricitystrongly chordal graphsdynamic algorithms\(h\)-indexcop-win graphsdiamond-free graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Cites Work

• Efficient graph representations
• Vertex-to-vertex pursuit in a graph
• Finding and counting given length cycles
• Matrix multiplication via arithmetic progressions
• Doubly lexical ordering of dense 0--1 matrices
• Three Partition Refinement Algorithms
• Characterizations of strongly chordal graphs
• On uniquely intersectable graphs
• Coloring perfect \((K_ 4\)-e)-free graphs
• Finding and counting small induced subgraphs efficiently
• Arboricity and Subgraph Listing Algorithms
• Clique graphs and Helly graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Recognizing quasi-triangulated graphs.
• Recognition algorithm for diamond-free graphs
• The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the complexity of fixed parameter clique and dominating set

Cited In (12)

• Extended dynamic subgraph statistics using \(h\)-index parameterized data structures
• Extended dynamic subgraph statistics using \(h\)-index parameterized data structures
• Comparability digraphs: an analogue of comparability graphs
• The complexity of growing a graph
• A unified approach to recognize squares of split graphs
• Local community detection based on small cliques
• The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics
• Fully dynamic arboricity maintenance
• Fully dynamic arboricity maintenance
• Graphs whose vertices of degree at least 2 lie in a triangle
• Improved dynamic graph coloring
• The complexity of growing a graph

This page was built for publication: Arboricity, \(h\)-index, and dynamic algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q418737)