Repository navigation
(MPQ-Tree Algorithm) Add a certifying algorithm for interval graph checking #28
Description
Activity
We want to use this algorithm. It refers to this algorithm.
More references: https://www.sciencedirect.com/science/article/pii/S0022000076800451
I have tried to comprehend the recognition algorithm to a more code-like algorithm
Some explenation:
T is an MPQ Tree
o is calculated by the ChordalityInspector Class of JgraphT
Adj(u) are the predecessors according to o
N/N./N* are nodes in the tree
V(N) are the nodes in the graph of the node N in the tree
A/B are sets of nodes the graphThe tree has a size of O(|V|) (according to the paper). The algorithm runs in O(|V|+|E|) somehow.
#init -calculate perfect elimination order o -Let T be the MPQ Tree -for all vertex u in o -special case for Adj(u) is empty #labeling phase -label every vertex in T with 1 if it has a neighbour of u -label every vertex in T with inf if it has only neighbours of u #test label -all nodes with positive label are a path -all Q nodes N with positive label have an outer section containing Adj(u) intersection V(N) #else G is not an interval graph #update phase -Let Path be the path of all positive labels from root to a leaf -Let N. be the lowest positive node in Path -Let N* be the highest non inf P-Node/Section in Path if Path contains nonempty P-Node/section above N. without inf label, else N*=N. -case 1: Path only has nonempty inf labels. add u to the leaf of Path (fig 5, L1) -case 2: Path has nonempty not-inf label. traverse bottom-up from N. to N*, current Node N: -partition V(N) into A, adjacent to u, and B, not adjacent to u) -template match with a case (fig4-7)Edit: Added some further explanation
We now can use the branch mpqIntervalRecognizer
- changed the title
[-]Add a certifying algorithm for interval graph checking[/-][+](MPQ-Tree Algorithm) Add a certifying algorithm for interval graph checking[/+]on Jul 13, 2018 I will work on computing the certificates:
- the interval representation of the graph from the resulting MPQ Tree as a positive certificate
- the AT-Triple of the graph from the last MPQ Tree as a negative certificate
labelling and testing phases are completely implemented.
works left up to now
- integrate Q-node templates
- check the necessity of the HashSet usage on the bag, replace with it when necessary
- examine again the actual time complexity of the implementation
- write more test cases for the implementation
Edit by PhoenixIra:
ToDo list:
To be done by Jiong:
To be done by Dia:
To be done by Ira: