Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorial algorithm

  1. May 22, 2015 #1
    Given a matrix A of a regular graph G. The matrix A can be divided into 4 sub matrices based on adjacency of vertex ##x \in G##.

    ## A_x## is the symmetric matrix of the graph ##(G-x)##, where ##C## is the symmetric matrix of the graph created by vertices of ##(G-x)## which are adjacent to ##x## and ##D## is the symmetric matrix of the graph created by vertices of ##(G-x)## which are not adjacent to ##x##.

    http://i.stack.imgur.com/qL2rD.jpg

    ## A_x = \left( \begin{array}{cc}

    C & E \\

    E^{T} & D\\

    \end{array} \right) ##





    It should be noted, that-



    1. Interchanging/swapping any two rows (or columns) of ##C## does not affect matrix ##D## (and vice versa).



    2. Any change in ##C## or ##D## or both ##C## and ##D## changes matrix ##E##.



    **Problem:** If some vertices of ##G## is rearranged(i.e. permuted), ##A## will be different, say, this new matrix is ##B##. Again, matrix ##B## can be divided into 4 sub matrices based on adjacency of vertex ##x \in G## and ## B_x## can be obtained.


    Assume-

    1. ##C## is always a regular graph’s matrix and bigger than ##D##.

    2. There exists an algorithm that always order ##D##(for a vertex ##x \in G##) takes ##K## times(assumed to be polynomial).

    3. Each row of E has different permutation, i.e. , rows might have same number of 1's but there is no two rows which can be permuted to each other. Say, ##r_x , r_y## are two rows, there is no permutation ##\sigma## so that, ## \sigma r_x=\sigma r_y##. *So, there is no way ##E## to be a zero matrix or matrix of all 1's or a matrix has some identical rows.*





    For ##n## vertices there will be total ##n## numbers of ##C,D##, each of them will take ##K##(assumed to be polynomial) time to sort. If Each ##C## takes ##f## time to sort, then the total complexity will be ##n\times K\times f##.



    **according to above 3 assumptions, Does there exist a polynomial time algorithm to sort ##C## so that ##B=A##? i.e. Is there a polynomial##f## ?**
     
  2. jcsd
  3. May 23, 2015 #2

    Drakkith

    User Avatar

    Staff: Mentor

  4. May 24, 2015 #3
    that discussion was incomplete and was the general case, this more specific. It would easier, if this thread is concluded.
     
  5. May 24, 2015 #4

    Mark44

    Staff: Mentor

  6. May 26, 2015 #5
    Consider ##G## as a strongly ##k## regular graph G(srg(##n,k,\lambda ,\mu##);##\lambda ,\mu >0##).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Combinatorial algorithm
  1. Combinatorial Question (Replies: 17)

  2. Combinatorial question (Replies: 8)

  3. Combinatorial Problem (Replies: 1)

Loading...