Memory efficient algorithms for cactus graphs and block graphs

DOI10.1016/J.DAM.2015.10.032MaRDI QIDQ528335zbMATH OpenOpenAlexFDO

Authors 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 pathcactus graphchromatic polynomialblock graphconstant-work-space algorithmin-place algorithm

Mathematics Subject Classification ID

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

Recommendations

• An optimal algorithm to find maximum and minimum height spanning trees on cactus graphs
• Constant-work-space algorithms for shortest paths in trees and simple polygons
• Space-efficient basic graph algorithms
• An optimal algorithm to find maximum independent set and maximum 2-independent set on cactus graphs
• Memory-constrained algorithms for simple polygons

Cites work

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

Cited in

(6)

• Relating the total domination number and the annihilation number of cactus graphs and block graphs
• An optimal algorithm to find maximum and minimum height spanning trees on cactus graphs
• Intersections and circuits in sets of line segments
• Token shifting on graphs
• Brill-Noether conjecture on cactus graphs
• Relating the annihilation number and the 2-domination number of block graphs

Describes a project that uses

Uses Software

• Algorithm 97

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

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