Graph extensions and some optimization problems in sparse matrix computations

MaRDI QIDQ2767414zbMATH OpenFDO

Authors Yixun Lin

Publication date 29 January 2002

Published in Advances in Mathematics (Beijing) (Search for Journal in Brave)

zbMATH Keywords

computational complexityelimination, graph labelinggraph extensionoptimizationpolynom-time algorithmssparse matrix computationssparse matrix storage

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational methods for sparse matrices (65F50)

Review text

The author presents theoretic approaches for a class of optimization problems from sparse matrix computations. These approaches facilitate the study in several aspects, as follows. The first aspect is the computational complexity. Some results are obtained on the complexity by using the relations between problems in different areas. By using the neighbourhood representations efficient heuristic algorithms are designed. Further special cases are studied for which there exist polynom-time algorithms. Finally, relations between different graph-theoretic parameters are given.

Recommendations

• Estimation of sparse hessian matrices and graph coloring problems
• Decomposition in multidimensional Boolean-optimization problems with sparse matrices
• Making sparse matrices sparser: Computational results
• scientific article; zbMATH DE number 3905737
• scientific article; zbMATH DE number 2095795

Cited in

(6)

• Algebraic graph theory for sparse flexibility matrices
• Efficient algorithms for the d-dimensional rigidity matroid of sparse graphs
• Estimating the global density of graphs by a sparseness index
• scientific article; zbMATH DE number 2185598 (Why is no real title available?)
• scientific article; zbMATH DE number 4160517 (Why is no real title available?)
• Discrete isoperimetric method for bandwidth, pathwidth and treewidth of hypercubes

This page was built for publication: Graph extensions and some optimization problems in sparse matrix computations

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