Title :
An Algorithm Combining Graph-Reduction and Graph-Search for Workflow Graphs Verification
Author :
Lu, Kai ; Liu, Qiang
Author_Institution :
Tsinghua Univ., Beijing
Abstract :
Since the structural conflicts in workflow processes can lead to malfunctioning of workflow management systems, the problem should be detected before workflow processes are put into execution. In this paper, we propose a combined graph-reduction and graph-search algorithm "CWRS" to verify workflow graphs. This algorithm reduces a cyclic workflow graph to an acyclic workflow graph, and then verifies this acyclic workflow graph by using Mahanti-Sinnakkrishnan algorithm. Computational complexity of this algorithm is 0(E), where E refers to number of edges in a workflow graph. In comparison with others, our algorithm can verify both cyclic and acyclic workflow graphs.
Keywords :
computational complexity; formal verification; graph theory; search problems; workflow management software; CWRS algorithm; Mahanti-Sinnakkrishnan algorithm; acyclic workflow graph; computational complexity; graph reduction; graph searching; structural conflicts; workflow graphs verification; workflow management systems; Algorithm design and analysis; Automation; Collaborative work; Computational complexity; Computer applications; Computer errors; Costs; Error correction; Safety; Workflow management software; Local Safety Cyclic Graph; Simple Loop; Workflow Graph; Workflow Management; Workflow Verification;
Conference_Titel :
Computer Supported Cooperative Work in Design, 2007. CSCWD 2007. 11th International Conference on
Conference_Location :
Melbourne, Vic.
Print_ISBN :
1-4244-0963-2
Electronic_ISBN :
1-4244-0963-2
DOI :
10.1109/CSCWD.2007.4281534