Memory efficient algorithms for cactus graphs and block graphs

DOI10.1016/j.dam.2015.10.032zbMath1361.05126OpenAlexW2178434937MaRDI QIDQ528335

Boris Brimkov, Illya V. Hicks

Publication date: 12 May 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.10.032

zbMATH Keywords

shortest pathchromatic polynomialblock graphcactus graphconstant-work-space algorithmin-place algorithm

Mathematics Subject Classification ID

Graph polynomials (05C31) Applications of graph theory (05C90) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Token shifting on graphs ⋮ Relating the annihilation number and the 2-domination number of block graphs ⋮ Relating the total domination number and the annihilation number of cactus graphs and block graphs ⋮ Brill-Noether conjecture on cactus graphs ⋮ Intersections and circuits in sets of line segments

Uses Software

• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Log-space algorithms for paths and matchings in \(k\)-trees
• Space-efficient geometric divide-and-conquer algorithms
• The hitting and cover times of Metropolis walks
• The theory of convex geometries
• Enumeration of \(m\)-ary cacti
• Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time
• Constant-Work-Space Algorithms for Shortest Paths in Trees and Simple Polygons
• Constant-Working-Space Algorithms: How Fast Can We Solve Problems without Using Any Extra Array?
• Undirected connectivity in log-space
• Technical Note—Reducing Space Requirements for Shortest Path Problems
• On chromaticity of graphs
• Shortest-Path-Finder Algorithm in a Two-Dimensional Array of Nonlinear Electronic Circuits
• Short random walks on graphs
• Towards in-place geometric algorithms and data structures
• Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
• Space efficient algorithms for directed series–parallel graphs
• On the Number of Husimi Trees

This page was built for publication: Memory efficient algorithms for cactus graphs and block graphs