How to find the Maximum Clique number of a Chordal graph from Perfect elimination ordering?

up vote
0
down vote

favorite

For the past 2 days, I have been research on the web to try and understand and code how to find the Clique number of a chordal graph. I came to know that we need to use LexBFS to find the Perfect elimination ordering first and then traverse this sequence to find the maximum clique of the Chordal graph.

So far my understanding is as follows:

Use LexBFS algorithm to find out an ordering.

Reverse the above ordering of vertices to obtain the Perfect elimination ordering.

Unfortunately, even after lot's of research on the web, I am not able to find a single page where it explains how to traverse or use the Perfect elimination ordering to find the Maximum clique in SIMPLE language (may, with an example/pseudocode and less math).

For example, if I have a Chordal graph as follows:

enter image description here

Using LexBFS I found the LexBFS ordering as 2,3,4,5,1 which on reverse is 1,5,4,3,2 which is supposed to be my Perfect elimination ordering.

Following is the iteration detail of how I obtained 2,3,4,5,1 mentioned above:

ordering = 
queueOfsets = [1,2,3,4,5]

itr1: 
 picked 2
 new ordering = [2]
 new queueOfsets = [1,3, 4,5]

itr2:
 picked 3
 new ordering = [2,3]
 new queueOfsets = [1,4, 5]

itr3: 
 picked 4
 new ordering = [2,3,4]
 new queueOfsets = [1,5]

itr4:
 picked 5
 new ordering = [2,3,4,5]
 new queueOfsets = [1]

itr5: 
 picked 1
 new ordering = [2,3,4,5,1]
 new queueofSet =

NOTE: As it is not yet clear to me on which element to be picked from the first set of queueofSet, I am picking "any" one of the available vertex in the first set of queueofSet.
(NEED A CONFIRMATION ON THIS APPROACH TOO, to know if I am doing it correctly.)

However, when I traverse this list from left to right, for 1, it is adjacent to 2,3,4,5 which are again right to 1 in the PEO but 1,2,3,4,5 is not a Clique.

Please let me know what is the correct way to traverse a PEO and what am I missing in my above traversal?

Any help is much appreciated. Thank you.

edited Jul 15 at 7:31

asked Jul 15 at 6:41

user3243499

180110

add a commentÂ |Â

up vote
0
down vote

favorite

So far my understanding is as follows:

Use LexBFS algorithm to find out an ordering.

Reverse the above ordering of vertices to obtain the Perfect elimination ordering.

For example, if I have a Chordal graph as follows:

enter image description here

Using LexBFS I found the LexBFS ordering as 2,3,4,5,1 which on reverse is 1,5,4,3,2 which is supposed to be my Perfect elimination ordering.

Following is the iteration detail of how I obtained 2,3,4,5,1 mentioned above:

ordering = 
queueOfsets = [1,2,3,4,5]

itr1: 
 picked 2
 new ordering = [2]
 new queueOfsets = [1,3, 4,5]

itr2:
 picked 3
 new ordering = [2,3]
 new queueOfsets = [1,4, 5]

itr3: 
 picked 4
 new ordering = [2,3,4]
 new queueOfsets = [1,5]

itr4:
 picked 5
 new ordering = [2,3,4,5]
 new queueOfsets = [1]

itr5: 
 picked 1
 new ordering = [2,3,4,5,1]
 new queueofSet =

However, when I traverse this list from left to right, for 1, it is adjacent to 2,3,4,5 which are again right to 1 in the PEO but 1,2,3,4,5 is not a Clique.

Please let me know what is the correct way to traverse a PEO and what am I missing in my above traversal?

Any help is much appreciated. Thank you.

edited Jul 15 at 7:31

asked Jul 15 at 6:41

user3243499

180110

add a commentÂ |Â

up vote
0
down vote

favorite

So far my understanding is as follows:

Use LexBFS algorithm to find out an ordering.

Reverse the above ordering of vertices to obtain the Perfect elimination ordering.

For example, if I have a Chordal graph as follows:

enter image description here

Using LexBFS I found the LexBFS ordering as 2,3,4,5,1 which on reverse is 1,5,4,3,2 which is supposed to be my Perfect elimination ordering.

Following is the iteration detail of how I obtained 2,3,4,5,1 mentioned above:

ordering = 
queueOfsets = [1,2,3,4,5]

itr1: 
 picked 2
 new ordering = [2]
 new queueOfsets = [1,3, 4,5]

itr2:
 picked 3
 new ordering = [2,3]
 new queueOfsets = [1,4, 5]

itr3: 
 picked 4
 new ordering = [2,3,4]
 new queueOfsets = [1,5]

itr4:
 picked 5
 new ordering = [2,3,4,5]
 new queueOfsets = [1]

itr5: 
 picked 1
 new ordering = [2,3,4,5,1]
 new queueofSet =

However, when I traverse this list from left to right, for 1, it is adjacent to 2,3,4,5 which are again right to 1 in the PEO but 1,2,3,4,5 is not a Clique.

Please let me know what is the correct way to traverse a PEO and what am I missing in my above traversal?

Any help is much appreciated. Thank you.

edited Jul 15 at 7:31

asked Jul 15 at 6:41

user3243499

180110

So far my understanding is as follows:

Use LexBFS algorithm to find out an ordering.

Reverse the above ordering of vertices to obtain the Perfect elimination ordering.

For example, if I have a Chordal graph as follows:

enter image description here

Using LexBFS I found the LexBFS ordering as 2,3,4,5,1 which on reverse is 1,5,4,3,2 which is supposed to be my Perfect elimination ordering.

Following is the iteration detail of how I obtained 2,3,4,5,1 mentioned above:

ordering = 
queueOfsets = [1,2,3,4,5]

itr1: 
 picked 2
 new ordering = [2]
 new queueOfsets = [1,3, 4,5]

itr2:
 picked 3
 new ordering = [2,3]
 new queueOfsets = [1,4, 5]

itr3: 
 picked 4
 new ordering = [2,3,4]
 new queueOfsets = [1,5]

itr4:
 picked 5
 new ordering = [2,3,4,5]
 new queueOfsets = [1]

itr5: 
 picked 1
 new ordering = [2,3,4,5,1]
 new queueofSet =

However, when I traverse this list from left to right, for 1, it is adjacent to 2,3,4,5 which are again right to 1 in the PEO but 1,2,3,4,5 is not a Clique.

Please let me know what is the correct way to traverse a PEO and what am I missing in my above traversal?

Any help is much appreciated. Thank you.

edited Jul 15 at 7:31

asked Jul 15 at 6:41

user3243499

180110

edited Jul 15 at 7:31

asked Jul 15 at 6:41

user3243499

180110

asked Jul 15 at 6:41

user3243499

180110

asked Jul 15 at 6:41

user3243499

180110

add a commentÂ |Â

active

oldest

votes

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\$","\$"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);

);

draft saved

draft discarded

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2852238%2fhow-to-find-the-maximum-clique-number-of-a-chordal-graph-from-perfect-eliminatio%23new-answer', 'question_page');

);

Post as a guest

Name

active

oldest

votes

draft saved

draft discarded

draft saved

draft discarded

Post as a guest

Name

Search This Blog

ukmuiik