Sign in to follow this  

Graph reduction to complete subgraphs

This topic is 2848 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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

This topic is 2848 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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