A note on mixed tree coloring

In this note we observe that the problem of mixed graph coloring can be solved in linear time for trees, which improves the quadratic algorithm of Hansen et al. [P. Hansen, J. Kuplinsky, D. de Werra, Mixed graph colorings, Math. Methods Oper. Res. 45 (1997) 145-160].     

一个基于持续消息的分布式工作流管理模型

提出了一种新的分布式结构,在这个结构中,排除了工作流系统对一个集中式数据库的依赖,而是用持续消息的方法将与过程执行有关的信息存储起来,使过程的执行是完全分布式的,并且每个节点都是各自独立的。采用这种方式能增强对错误的恢复能力以及构造系统的灵活性和扩展性。     

A distance measure for large graphs based on prime graphs

Graphs are universal modeling tools. They are used to represent objects and their relationships in almost all domains: they are used to represent DNA, images, videos, social networks, XML documents, etc. When objects are represented by graphs, the problem of their comparison is a problem of comparing graphs. Comparing objects is a key task in our daily life. It is the core of a search engine, the backbone of a mining tool, etc. Nowadays, comparing objects faces the challenge of the large amount of data that this task must deal with. Moreover, when graphs are used to model these objects, it is known that graph comparison is very complex and computationally hard especially for large graphs. So, research on simplifying graph comparison gainedan interest and several solutions are proposed. In this paper, we explore and evaluate a new solution for the comparison of large graphs. Our approach relies on a compact encoding of graphs called prime graphs. Prime graphs are smaller and simpler than the original ones but they retain the structure and properties of the encoded graphs. We propose to approximate the similarity between two graphs by comparing the corresponding prime graphs. Simulations results show that this approach is effective for large graphs.     

Improving process models by discovering decision points

Workflow management systems (WfMS) are widely used by business enterprises as tools for administrating, automating and scheduling the business process activities with the available resources. Since the control flow specifications of workflows are manually designed, they entail assumptions and errors, leading to inaccurate workflow models. Decision points, the XOR nodes in a workflow graph model, determine the path chosen toward completion of any process invocation. In this work, we show that positioning the decision points at their earliest points can improve process efficiency by decreasing their uncertainties and identifying redundant activities. We present novel techniques to discover the earliest positions by analyzing workflow logs and to transform the model graph. The experimental results show that the transformed model is more efficient with respect to its average execution time and uncertainty, when compared to the original model.     

Mining unconnected patterns in workflows

General patterns of execution that have been frequently scheduled by a workflow management system provide the administrator with previously unknown, and potentially useful information, e.g., about the existence of unexpected causalities between subprocesses of a given workflow. This paper investigates the problem of mining unconnected patterns on the basis of some execution traces, i.e., of detecting sets of activities exhibiting no explicit dependency relationships that are frequently executed together. The problem is faced in the paper by proposing and analyzing two algorithms. One algorithm takes into account information about the structure of the control-flow graph only, while the other is a smart refinement where the knowledge of the frequencies of edges and activities in the traces at hand is also accounted for, by means of a sophisticated graphical analysis. Both algorithms have been implemented and integrated into a system prototype, which may profitably support the enactment phase of the workflow. The correctness of the two algorithms is formally proven, and several experiments are reported to evidence the ability of the graphical analysis to significantly improve the performances, by dramatically pruning the search space of candidate patterns.     

一种基于XML的工作流过程定义语言研究与应用

针对目前工作流过程描述语言灵活性不够的问题,从工作流系统的Web化以及适应异构应用环境角度出发,将工作流过程定义与工作流执行相分离,继承了WfMC的XPDL标准和XML的优点,提蹬了一种基于XML的工作流定义语言XML—WfPDL,并介绍了语言的设计思想、主要概念及实现的相关技术。最后,给出了利用该语言开发实现的一个网上审批软件系统。     

基于工作流的高速公路养护系统的设计与实现

高速公路养护工作因为其数据复杂、业务变化频繁而较难管理。同时市场竞争与用户的压力在不断促使管理求变,因此高速公路养护管理系统不得不快速适应这种不断变化的需求。由于使用工作流技术构建的信息系统具有很好的灵活性、良好的可扩展能力等,利用工作流技术来实现高速公路养护管理系统是非常好的选择。本文对如何利用工作流技术来实现一个养护管理系统作了详细的分析与设计,并对采用工作流技术带来的优点作了详细的分析。实践证明了本系统的设计思想是有意义的,并对开发同类系统具有参考价值。     

基于工作流的高速公路养护系统的设计与实现

高速公路养护工作因为其数据复杂、业务变化频繁而较难管理。同时市场竞争与用户的压力在不断促使管理求变，因此高速公路养护管理系统不得不快速适应这种不断变化的需求。由于使用工作流技术构建的信息系统具有很好的灵活性、良好的可扩展能力等，利用工作流技术来实现高速公路养护管理系统是非常好的选择。本文对如何利用工作流枝术来实现一个养护管理系统作了详细的分析与设计，并对采用工作流技术带来的优．最作了详细的分析。实践证明了本系统的设计思想是有意义的，并对开发同类系统具有参考价值。     

A refined search tree technique for Dominating Set on planar graphs

We establish a refined search tree technique for the parameterized DOMINATING SET problem on planar graphs. Here, we are given an undirected graph and we ask for a set of at most k vertices such that every other vertex has at least one neighbor in this set. We describe algorithms with running times O(8^kn) and O(8^kk+n³), where n is the number of vertices in the graph, based on bounded search trees. We describe a set of polynomial time data-reduction rules for a more general “annotated” problem on black/white graphs that asks for a set of k vertices (black or white) that dominate all the black vertices. An intricate argument based on the Euler formula then establishes an efficient branching strategy for reduced inputs to this problem. In addition, we give a family examples showing that the bound of the branching theorem is optimal with respect to our reduction rules. Our final search tree algorithm is easy to implement; its analysis, however, is involved.     

基于工作流技术的航材保障系统

针对未来信息化战争对航材保障的效率提出的更高要求,对工作流技术和航材保障研究现状进行分析,建立将工作流技术应用到航材保障中的生命周期图,并研究生命周期的每一环节。应用工作流技术对于航材保障势必产生巨大的军事效益。     

Finding bipartite subgraphs efficiently

Polynomial algorithms are given for the following two problems:

•

given a graph with n vertices and m edges, find a complete balanced bipartite subgraph Kq,q with ,

•

given a graph with n vertices, find a decomposition of its edges into complete balanced bipartite graphs having altogether O(n²/lnn) vertices.

The first algorithm can be modified to have running time linear in m and find a Kq^′,q^′ with q^′=⌊q/5⌋. Previous proofs of the existence of such objects, due to K?vári, Sós and Turán (1954) [10], Chung, Erd?s and Spencer (1983) [5], Bublitz (1986) [4] and Tuza (1984) [13] were non-constructive.     

Graphix a graph theory sub language

GRAPHIX is a PASCAL based graph theory sub-language. It provides a set of graph theory algorithms, and allows the user to program directly in terms of graph structures theory algorithms, and allows the user to program directly in terms of graph structures with no knowledge of the internal representation of the graph. A preprocessor has been written to convert GRAPHIX/PASCAL programs into pure PASCAL. The main problems of a sub-language and preprocessing have been overcome in the design of the language and the preprocessor. An example of a GRAPHIX/PASCAL program is provided.     

虚拟企业中的工作流管理系统框架研究

MfMC为工作流管理系统提出的一系列标准，在企业内部信息集成中起到了重要的规范作用。在虚拟企业环境下，要求完全分布式的工作流系统间的集成。本文分析了虚拟企业环境对工作管理系统的要求和传统参考模型的缺陷，提出了一个二阶段的动态工作流扩展框架，试图支持扩展工作流模型克服原有系统的缺陷，以改善工作流的柔性。     

空间信息服务链模型的有向图表示及其验证

由于目前通用的Web服务组合语言不适合地理信息处理业务流程的直观表达,且学习成本高,不适合空间信息领域的用户使用,因此建立了一种基于有向图的空间信息服务链模型,并从模型组成元素、约束条件和控制模式3个方面对其进行了详细定义和设计。针对构建的服务链模型,从模型语法正确性、结构正确性和语义正确性3个方面进行研究,通过对空间信息服务链模型结构的分析,结合现有的图规约规则,研究并设计了空间信息服务链模型的语法、结构和语义验证方法,并给出了模型验证方法的具体算法和实现流程。通过具体的案例分析,说明了所提出的算法和设计的实施流程的有效性和可操作性。     

Solving shortest paths efficiently on nearly acyclic directed graphs

Shortest path problems can be solved very efficiently when a directed graph is nearly acyclic. Earlier results defined a graph decomposition, now called the 1-dominator set, which consists of a unique collection of acyclic structures with each single acyclic structure dominated by a single associated trigger vertex. In this framework, a specialised shortest path algorithm only spends delete-min operations on trigger vertices, thereby making the computation of shortest paths through non-trigger vertices easier. A previously presented algorithm computed the 1-dominator set in O(mn) worst-case time, which allowed it to be integrated as part of an O(mn+nrlogr) time all-pairs algorithm. Here m and n respectively denote the number of edges and vertices in the graph, while r denotes the number of trigger vertices. A new algorithm presented in this paper computes the 1-dominator set in just O(m) time. This can be integrated as part of the O(m+rlogr) time spent solving single-source, improving on the value of r obtained by the earlier tree-decomposition single-source algorithm. In addition, a new bidirectional form of 1-dominator set is presented, which further improves the value of r by defining acyclic structures in both directions over edges in the graph. The bidirectional 1-dominator set can similarly be computed in O(m) time and included as part of the O(m+rlogr) time spent computing single-source. This paper also presents a new all-pairs algorithm under the more general framework where r is defined as the size of any predetermined feedback vertex set of the graph, improving the previous all-pairs time complexity from O(mn+nr²) to O(mn+r³).     

基于数据结构的最小生成树算法

数据结构是计算机科学的算法理论基础和软件设计的技术基础,在计算机领域中有着举足轻重的作用。本文以邻接矩阵作为图的存储结构,指出如何在计算机上实现克鲁斯卡尔算法,并分析所设计算法的时间复杂度。     

基于组件和工作流技术的系统模型

组件技术和工作流技术是两种不同的技术,该文讨论了它们相互结合,构建工作流组件的方法,并给出了基于组件和工作流技术的系统模型,对开发工作流系统有一定实用价值。