Why should biconnected components be identified first

DOI10.1016/0166-218X(93)90046-QMaRDI QIDQ1803675zbMATH OpenFDO

Authors Dorit S. Hochbaum

Publication date 29 June 1993

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

Full work available at URL https://doi.org/10.1016/0166-218X(93)90046-Q

zbMATH Keywords

biconnected componentsdecomposition procedure

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Review text

Most optimization algorithms for combinatorial problems on graphs assume that the graph is connected. The paper describes a decomposition procedure that reduces the solution for some problems solving them only on the biconnected components of the graph.

Recommendations

• An Efficient Parallel Biconnectivity Algorithm
• On the Strongly Connected and Biconnected Components of the Complement of Graphs
• The decomposition of graphs into \(k\)-connected components
• On the parallel computation of the biconnected and strongly connected co-components of graphs
• Graphs and graph algorithms

Cites work

• Efficient bounds for the stable set, vertex cover and set packing problems
• scientific article; zbMATH DE number 3633709 (Why is no real title available?)

Cited in

(5)

• Finding biconnected components in O(n) time for a class of graphs
• A two-level graph partitioning problem arising in mobile wireless communications
• Efficient reassembling of three-regular planar graphs
• A heuristic approach for dividing graphs into bi-connected components with a size constraint
• The impact of a bi-connected graph decomposition on solving cooperative path-finding problems

This page was built for publication: Why should biconnected components be identified first

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