Sign in to follow this  
Nick of ZA

Graph reduction to complete subgraphs

Recommended Posts

I can not answer your question, I am now interested though after having looked it up. This seems to have implications in how functional programming, such as Haskel, is implemented as is described by Wiki Graph Reduction! I can not find reference in my reference text but I probably have to look for more specific subjects. I can now add lazy evaluation to my list of needs to be researched; functional programming seems rather novel. May I ask why you are looking and what you are looking to do? If you don't mind!

Share this post


Link to post
Share on other sites
I think this should do:
* Pick the node with the smallest degree.
* Remove it and all the edges that touch it.
* Rinse, repeat.

In case you are not familiar with the term, the degree of a node is the number of edges that touch it.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
I think this should do:
* Pick the node with the smallest degree.
* Remove it and all the edges that touch it.
* Rinse, repeat.

In case you are not familiar with the term, the degree of a node is the number of edges that touch it.


Can you repeat that in Matrix?

Share this post


Link to post
Share on other sites
Quote:
Original post by Buttacup
Quote:
Original post by alvaro
I think this should do:
* Pick the node with the smallest degree.
* Remove it and all the edges that touch it.
* Rinse, repeat.

In case you are not familiar with the term, the degree of a node is the number of edges that touch it.


Can you repeat that in Matrix?


I don't understand. I didn't understand your previous post either, so I limited myself to answering the original question.

Share this post


Link to post
Share on other sites
Quote:
Original post by Buttacup
Can you repeat that in Matrix?


Ummmm? You mean this?:

I have an nxn adjacency matrix A. I multiply it by a vector of all ones. This gives me a vector of node degrees. I find which element of this vector is smallest -- say it's the k-th one. Then I delete the kth row and column of the adjacency matrix; this gives me a new (n-1)x(n-1) adjacency matrix.

Granted, I haven't thought at all about whether this algorithm works; all I did was "translate."

Share this post


Link to post
Share on other sites
Quote:
Original post by Emergent
Quote:
Original post by Buttacup
Can you repeat that in Matrix?


Ummmm? You mean this?:

I have an nxn adjacency matrix A. I multiply it by a vector of all ones. This gives me a vector of node degrees. I find which element of this vector is smallest -- say it's the k-th one. Then I delete the kth row and column of the adjacency matrix; this gives me a new (n-1)x(n-1) adjacency matrix.

Granted, I haven't thought at all about whether this algorithm works; all I did was "translate."


Nice, I will look that over this is pretty new to me!

I think this is where I'm headed. I'm also seeing some answers here to a question I posted in a previous thread elsewhere on how one would formulate a set of algorithms to solve a Chromatic Graph problem such as Sudoku! It would still be nice to know what the original poster was up to :D

[edit]
Canonical form of a matrix, for planarity testing <=== ahhhhhh

[Edited by - Buttacup on February 25, 2010 11:47:07 AM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this