The General Minimum Fill-In Problem

DOI10.1137/0608059MaRDI QIDQ3802913zbMATH OpenOpenAlexFDO

Authors Horst Wendel

Publication date 1987

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

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

zbMATH Keywords

Gaussian eliminationgraph-theoretical elimination processInitial Theoremload-flow calculationminimum fill-in problemoptimal orderingseparating setseparation approachsparse linear equationssystem of linear equationstearing a graph

Mathematics Subject Classification ID

Graph theory (05C99) Linear equations (linear algebraic aspects) (15A06) Direct numerical methods for linear systems and matrix inversion (65F05) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35)

Recommendations

• scientific article; zbMATH DE number 3844934
• Fast Computation of Minimal Fill Inside A Given Elimination Ordering
• On the Performance of the Minimum Degree Ordering for Gaussian Elimination
• A practical algorithm for making filled graphs minimal
• The decomposability of minimum fill-in problems for graphs

Cites work

• Algorithmic Aspects of Vertex Elimination on Graphs
• An Automatic Nested Dissection Algorithm for Irregular Finite Element Problems
• An Automatic One-Way Dissection Algorithm for Irregular Finite Element Problems
• Computing the Minimum Fill-In is NP-Complete
• scientific article; zbMATH DE number 3684855 (Why is no real title available?)
• scientific article; zbMATH DE number 3245483 (Why is no real title available?)
• scientific article; zbMATH DE number 3420184 (Why is no real title available?)
• Nested Dissection of a Regular Finite Element Mesh
• Network Flow and Testing Graph Connectivity
• Nonserial dynamic programming
• On the theory of the elimination process
• Solution of large sparse systems by ordered triangular factorization
• The Use of Linear Graphs in Gauss Elimination

Cited in

(8)

• A practical algorithm for making filled graphs minimal
• scientific article; zbMATH DE number 3844934 (Why is no real title available?)
• On the Performance of the Minimum Degree Ordering for Gaussian Elimination
• Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds
• scientific article; zbMATH DE number 2095795 (Why is no real title available?)
• The decomposability of minimum fill-in problems for graphs
• Minimizing elimination tree height can increase fill more than linearly
• Asymptotic constants in averaged Hölder inequalities

This page was built for publication: The General Minimum Fill-In Problem

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