The beta version of the PC tree report is finished. The topic is "PC tree and its application". This report first discuss the use of PC tree for testing consecutive-ones property of a 0-1 matrix. Then discuss its further application on interval graph recognition and planarity testing.
However, I start writing terribly when describing the application. If you don't understand what they are talking about, please feel free to ask me, I will fix it asap, but not today XD
PC tree and its application
Showing posts with label pc tree. Show all posts
Showing posts with label pc tree. Show all posts
20070505
20070411
PC-tree
Definition:
A circular-arc graph is the intersection graph of a family of arcs of a circle.Problem definition:
Given a graph G = (V, E), determine whether the graph is a circular-arc graph.PC-tree is a data structure used to solve the above problem, discovered by Hsu and McConnell. PC-tree is an unrooted tree, its previous version is called PQ-tree which is discovered by Booth and Lueker in 1976. This article will focus on PC-tree only, because PC-tree is generalization of PQ-tree, which means any problem that can be solved by PQ-tree can reduce to PC-tree problems.
Each circular-arc graph can be represented by a clique matrix. Consider circular arc its corresponding circular-arc graph and clique matrix as follow:
By theorem, a graph is circular-arc iff. its clique matrix must a circular-ones property (proof provide later). Now the problem is focusing on how to check a matrix contains circular one property. PC-tree take the place to solve this problem. Let me introduce what is a PC-tree first.
PC-tree has two kinds of internal node, P-node and C-node (that's why it is called PC-tree). The children of P-node can be arranged in any order (ie. all permutations). Other than P-node, the children of C-node can only be arranged in the original order or its reverse (ie. if it's leaves is "ABC", another possible ordering is "CBA"). PC-tree is built by considering the rows of clique matrix one by one. The outline of the algorithm is as follow:
for each row in clique matrix {assign the value to each row symbol; find a Terminal Path to separate 0s and 1s; align all 1s and 0s to the same side; split each node on the path into two nodes, one connect to the leaves with 1s and one connect to 0s; delete the edges of the path and replace with a C-node x; contract all edges from x to C-node neighbors, and any node has only 2 neighbors.
}
The circular-ones ordering can be discovered from the graph by reading the leaves on PC-tree in clockwise or anti-clockwise. Like the following:
img provide later
The time complexity of the O(|E|) (proof provide later).
Further application is: scheduling jobs, minimum coloring, maximum cliques, planarity test, consecutive-ones, ...
Subscribe to:
Posts (Atom)