Applications of a poset representation to edge connectivity and graph rigidity
- 9 December 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 26, 812-821
- https://doi.org/10.1109/sfcs.1991.185453
Abstract
A poset representation for a family of sets defined by a labeling algorithm is investigated. Poset representations are given for the family of minimum cuts of a graph, and it is shown how to compute them quickly. The representations are the starting point for algorithms that increase the edge connectivity of a graph, from lambda to a given target tau = lambda + delta , adding the fewest edges possible. For undirected graphs the time bound is essentially the best-known bound to test tau -edge connectivity; for directed graphs the time bound is roughly a factor delta more. Also constructed are poset representations for the family of rigid subgraphs of a graph, when graphs model structures constructed from rigid bars. The link between these problems is that they all deal with graphic matroids.Keywords
This publication has 14 references indexed in Scilit:
- A fast algorithm for optimally increasing the edge-connectivityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Augmenting graphs to meet edge-connectivity requirementsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A matroid approach to finding edge connectivity and packing arborescencesPublished by Association for Computing Machinery (ACM) ,1991
- Matroid Theory and its Applications in Electric Network Theory and in StaticsPublished by Springer Nature ,1989
- Forests, frames, and games: algorithms for matroid sums and applicationsPublished by Association for Computing Machinery (ACM) ,1988
- ON THE REPRESENTATION OF THE RIGID SUB-SYSTEMS OF A PLANE LINK SYSTEMJournal of the Operations Research Society of Japan, 1986
- Efficient algorithm for finding all minimal edge cuts of a nonoriented graphCybernetics and Systems Analysis, 1986
- NETWORK-FLOW ALGORITHMS FOR LOWER-TRUNCATED TRANSVERSAL POLYMATROIDSJournal of the Operations Research Society of Japan, 1983
- On the structure of all minimum cuts in a network and applicationsPublished by Springer Nature ,1980
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972