On some properties of the Laplacian matrix revealed by the RCM algorithm

descriptionPublicationkeyboard_double_arrow_right Article 01 Sep 2016 Spain English Publisher:Institute of Mathematics, Czech Academy of SciencesJournal:Czechoslovak Mathematical Journal, volume 66, pages 603-620 (issn: 0011-4642, eissn: 1572-9141,

Copyright policy )

Authors: Pedroche Sánchez, Francisco; Rebollo Pedruelo, Miguel; Carrascosa Casamayor, Carlos; Palomares Chust, Alberto;

doi: 10.1007/s10587-016-0281-y

On some properties of the Laplacian matrix revealed by the RCM algorithm

- Summary
- Subjects
- Related research
  (1)
- Metrics

Abstract

In this paper we present some theoretical results about the irreducibility of the Laplacian matrix ordered by the Reverse Cuthill-McKee (RCM) algorithm. We consider undirected graphs with no loops consisting of some connected components. RCM is a well-known scheme for numbering the nodes of a network in such a way that the corresponding adjacency matrix has a narrow bandwidth. Inspired by some properties of the eigenvectors of a Laplacian matrix, we derive some properties based on row sums of a Laplacian matrix that was reordered by the RCM algorithm. One of the theoretical results serves as a basis for writing an easy MATLAB code to detect connected components, by using the function “symrcm” of MATLAB. Some examples illustrate the theoretical results.

The research has been supported by Spanish DGI grant MTM2010-18674, Consolider Ingenio CSD2007-00022, PROMETEO 2008/051, OVAMAH TIN2009-13839-C03-01, and PAID-06-11-2084.

Country

Spain

Related Organizations

Universitat Politècnica de València
Spain

Keywords

graph partitioning, Graphs and linear algebra (matrices, eigenvalues, etc.), Ordering algorithm, Graph partitioning, Other matrix algorithms, ordering algorithm, reverse Cuthill-McKee algorithm, Reverse Cuthill-McKee algorithm, Computational methods for sparse matrices, MATEMATICA APLICADA, Laplacian matrix, LENGUAJES Y SISTEMAS INFORMATICOS

1 Research products, page 1 of 1

A direct comparison of three algorithms for reducing profile and wavefront
1989IsAmongTopNSimilarDocuments

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	2
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average