Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1128.68544
Dereniowski, Dariusz; Kubale, Marek
Cholesky factorization of matrices in parallel and ranking of graphs. (English)
[A] Wyrzykowski, Roman (ed.) et al., Parallel processing and applied mathematics. 5th international conference, PPAM 2003, Czȩstochowa, Poland, September 7--10, 2003. Revised papers. Berlin: Springer. Lecture Notes in Computer Science 3019, 985-992 (2004). ISBN 3-540-21946-3/pbk

Summary: The vertex ranking problem is closely related to the problem of finding the elimination tree of minimum height for a given graph. This implies that the problem has applications in the parallel Cholesky factorization of matrices. We describe the connection between this model of graph coloring and the matrix factorization. We also present a polynomial time algorithm for finding edge ranking of complete bipartite graphs. We use it to design an $O(m ^{2+d })$ algorithm for edge ranking of graphs obtained by removing $O(\log m)$ edges from a complete bipartite graph, where $d$ is a fixed number. Then we extend our results to complete $k$-partite graphs for any fixed $k>2$. In this way we give a new class of matrix factorization instances that can be optimally solved in polynomial time.

MSC 2000:: *68W10 Parallel algorithms
05C85 Graphic algorithms
65F30 Other matrix algorithms

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]