DocumentCode :
3150182
Title :
An Algorithm Combining Graph-Reduction and Graph-Search for Workflow Graphs Verification
Author :
Lu, Kai ; Liu, Qiang
Author_Institution :
Tsinghua Univ., Beijing
fYear :
2007
fDate :
26-28 April 2007
Firstpage :
772
Lastpage :
776
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;
fLanguage :
English
Publisher :
ieee
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
Type :
conf
DOI :
10.1109/CSCWD.2007.4281534
Filename :
4281534
Link To Document :
بازگشت