Algorithmic Aspects of Vertex Elimination on Directed Graphs
- 1 January 1978
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Applied Mathematics
- Vol. 34 (1), 176-197
- https://doi.org/10.1137/0134014
Abstract
Summary:The question of generalizing results involving chordal graphs to similar concepts for chordal bipartite graphs is addressed. First, it is found that the removal of a bisimplicial edge from a chordal bipartite graph produces a chordal bipartite graph. As consequence, occurance of arithmetic zeros will not terminate perfect Gaussian elimination on sparse matrices having associated a chordal bipartite graph. Next, a property concerning minimal edge separators is presented. Finally, it is shown that, to any vertex of a chordal bipartite graph an edge may be added such that the chordality is maintainedKeywords
This publication has 20 references indexed in Scilit:
- FINDING THE BLOCK LOWER TRIANGULAR FORM OF A SPARSE MATRIXPublished by Elsevier ,1976
- CONSIDERATIONS IN THE DESIGN OF SOFTWARE FOR SPARSE GAUSSIAN ELIMINATION**This research was supported in part by NSF Grant GJ-43157 and ONR Grant N0014-67-A-0097-0016.Published by Elsevier ,1976
- Regular Algebra Applied to Path-finding ProblemsIMA Journal of Applied Mathematics, 1975
- Partitioning, tearing and modification of sparse linear systemsJournal of Mathematical Analysis and Applications, 1974
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite GraphsSIAM Journal on Computing, 1973
- Toward Characterization of Perfect Elimination DigraphsSIAM Journal on Computing, 1973
- The Transitive Reduction of a Directed GraphSIAM Journal on Computing, 1972
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972
- An Algebra for Network Routing ProblemsIMA Journal of Applied Mathematics, 1971
- Symbolic Generation of an Optimal Crout Algorithm for Sparse Systems of Linear EquationsJournal of the ACM, 1970