Adjacency queries in dynamic sparse graphs

DOI10.1016/j.ipl.2006.12.006zbMath1184.68202OpenAlexW2041955583MaRDI QIDQ846004

Ł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)

Related Items (8)

Simultaneously load balancing for every p-norm, with reassignments ⋮ A \(13k\)-kernel for planar feedback vertex set via region decomposition ⋮ Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries ⋮ Fully dynamic MIS in uniformly sparse graphs ⋮ A simple greedy algorithm for dynamic graph orientation ⋮ Fully dynamic arboricity maintenance ⋮ Unnamed Item ⋮ Improved Dynamic Graph Coloring

Cites Work

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

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