A Note on the NP-Completeness of Vertex Elimination on Directed Graphs

DOI10.1137/0601033zbMath0496.68030OpenAlexW2090912645MaRDI QIDQ3960119

John R. Gilbert

Publication date: 1980

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0601033

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Direct numerical methods for linear systems and matrix inversion (65F05) Directed graphs (digraphs), tournaments (05C20)

Related Items (3)

On optimality preserving eliminations for the minimum edge count and optimal Jacobian accumulation problems in linearized DAGs ⋮ A survey of direct methods for sparse linear systems ⋮ On lower bounds for optimal Jacobian accumulation

Cites Work

• Algorithmic Aspects of Vertex Elimination on Directed Graphs

This page was built for publication: A Note on the NP-Completeness of Vertex Elimination on Directed Graphs