Memory efficient algorithms for cactus graphs and block graphs
DOI10.1016/J.DAM.2015.10.032zbMATH Open1361.05126OpenAlexW2178434937MaRDI QIDQ528335FDOQ528335
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
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
shortest pathcactus graphchromatic polynomialblock graphconstant-work-space algorithmin-place algorithm
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)
Cites Work
- Title not available (Why is that?)
- Undirected connectivity in log-space
- On chromaticity of graphs
- The theory of convex geometries
- Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
- Log-space algorithms for paths and matchings in \(k\)-trees
- 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
- Towards in-place geometric algorithms and data structures
- On the Number of Husimi Trees
- Space-efficient geometric divide-and-conquer algorithms
- Enumeration of \(m\)-ary cacti
- Constant-Working-Space Algorithms: How Fast Can We Solve Problems without Using Any Extra Array?
- Technical Note—Reducing Space Requirements for Shortest Path Problems
- Title not available (Why is that?)
- Shortest-Path-Finder Algorithm in a Two-Dimensional Array of Nonlinear Electronic Circuits
- Short random walks on graphs
- Space efficient algorithms for directed series–parallel graphs
- The hitting and cover times of Metropolis walks
Cited In (6)
- 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
- Relating the total domination number and the annihilation number of cactus graphs and block graphs
Uses Software
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)
