My Math Forum Find max size of clique in permutation graph
 User Name Remember Me? Password

 Probability and Statistics Basic Probability and Statistics Math Forum

 October 2nd, 2015, 08:00 AM #1 Newbie   Joined: Oct 2015 From: Poland Posts: 1 Thanks: 0 Find max size of clique in permutation graph Hello, I have following problem. I have following graph: 1 3 1 5 1 4 2 4 2 3 2 5 3 4 which looks like below I want to calculate permutation for this graph. My result is: (4 3 5 1 2) But it looks that is wrong answer. Size of the largest clique in permutation graph is equal to the longest decreasing subsequence of permutation. The longest decreasing subsequence of my permutation is 2, when the largest clique has size equals to 3. Could you please help me with this issue? I would appreciaty any help that you can provide. Best regards Antek
 October 2nd, 2015, 06:32 PM #2 Senior Member   Joined: Oct 2013 From: New York, USA Posts: 632 Thanks: 85 I'm not sure I understand the question. If by permutations you mean how many line segments met each point, just count the frequency of each number in the original list, making the answer (3 3 3 3 2).

 Tags clique, find, graph, max, permutation, size

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Kamster Geometry 0 April 22nd, 2014 09:42 PM BenFRayfield Applied Math 4 December 21st, 2013 11:58 PM experiware Applied Math 1 June 17th, 2013 01:52 PM rayman Abstract Algebra 5 January 29th, 2012 02:26 AM Singularity Applied Math 1 April 15th, 2011 07:42 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top