Adjacency queries in dynamic sparse graphs

DOI10.1016/J.IPL.2006.12.006MaRDI QIDQ846004zbMATH OpenOpenAlexFDO

Authors Łukasz Kowalik

Publication date 29 January 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2006.12.006

zbMATH Keywords

dynamicdata structuresgraph algorithmsorientationadjacency

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Recommendations

• Dynamic graph connectivity in polylogarithmic worst case time
• Fully dynamic arboricity maintenance
• scientific article; zbMATH DE number 1256641
• Sparsification—a technique for speeding up dynamic graph algorithms
• Fully dynamic arboricity maintenance

Cites work

• scientific article; zbMATH DE number 2185626 (Why is no real title available?)
• Algorithms and Data Structures
• Algorithms – ESA 2004
• Decomposition of Finite Graphs Into Forests
• Dynamic Perfect Hashing: Upper and Lower Bounds
• On the Complexity of a Game Related to the Dictionary Problem
• Optimal bounds for the predecessor problem and related problems
• Oracles for bounded-length shortest paths in planar graphs
• Planar orientations with low out-degree and compaction of adjacency matrices
• Surpassing the information theoretic bound with fusion trees
• Tight(er) worst-case bounds on dynamic searching and priority queues

Cited in

(14)

• A simple greedy algorithm for dynamic graph orientation
• A dynamic data structure for counting subgraphs in sparse graphs
• Fully dynamic MIS in uniformly sparse graphs
• A 13k-kernel for planar feedback vertex set via region decomposition
• Arboricity, \(h\)-index, and dynamic algorithms
• Simultaneously load balancing for every \(p\)-norm, with reassignments
• Efficient single-pair all-shortest-path query processing for massive dynamic networks
• Improved dynamic colouring of sparse graphs
• A simple greedy algorithm for dynamic graph orientation
• Fully dynamic arboricity maintenance
• Fully dynamic arboricity maintenance
• scientific article; zbMATH DE number 1256641 (Why is no real title available?)
• Improved dynamic graph coloring
• Orienting dynamic graphs, with applications to maximal matchings and adjacency queries

This page was built for publication: Adjacency queries in dynamic sparse graphs

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