Algorithmic Aspects of Vertex Elimination on Directed Graphs

DOI10.1137/0134014zbMath0377.65013OpenAlexW2089341221MaRDI QIDQ4155746

Robert Endre Tarjan, Donald J. Rose

Publication date: 1978

Published in: SIAM Journal on Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/2fc1ecb3e8e2e2bb40a85aac57f55be03e3c7b5f

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Directed graphs (digraphs), tournaments (05C20)

Related Items

Minimal fill in O(\(n^{2.69}\)) time, On optimality preserving eliminations for the minimum edge count and optimal Jacobian accumulation problems in linearized DAGs, Search-space size in contraction hierarchies, Sparse linear problems and the least squares method, On strictly chordality-\(k\) graphs, A note on perfect partial elimination, Chordal digraphs, Reordering Strategy for Blocking Optimization in Sparse Linear Solvers, Degree switching operations in networks and large scale systems assignment problems, Determinantal formulae and nonsymmetric gaussian perfect elimination, The importance of structure in incomplete factorization preconditioners, Digraphs of bounded elimination width, Digraph measures: Kelly decompositions, games, and orderings, Recognizing Sparse Perfect Elimination Bipartite Graphs, Inherited Matrix Entries: Principal Submatrices of the Inverse, A survey of direct methods for sparse linear systems, On the ordering of sparse linear systems, Deterministic inverse zero-patterns, On lower bounds for optimal Jacobian accumulation, Unnamed Item, Computational complexity of some intelligent computing systems, Several results on chordal bipartite graphs, Iterative methods for linear systems of equations: A brief historical journey, Positive definite completions of partial Hermitian matrices, Combinatorial analysis (nonnegative matrices, algorithmic problems), Recognizing badly presented \(Z\)-modules, Predicting the structure of sparse orthogonal factors, A Note on the NP-Completeness of Vertex Elimination on Directed Graphs, Computing the Minimum Fill-In is NP-Complete