检索结果-内蒙古大学图书馆

4th International Conference on Internet and Web Applications and Services

作者： Ma, Zhilei Lu, Wei Leymann, Frank Univ Stuttgart Inst Architecture Applicat Syst D-70569 Stuttgart Germany

ISBN: (纸本)9781424438518

Reuse of proven process models increases modeling efficiency;and ensure the quality if process models. To provide a better support for reuse, the retrieval mechanisms of process repositories should be able to propose similar process models that ranked according to their similarity degrees to the query request. As a process model and a query request on process structure can both be viewed as rooted, directed, and acyclic graphs, the problem of querying structural in formation of BPEL processes can be reduced to a graph matchmaking problem. In this paper we present a novel and efficient graph-based algorithm for querying structural information of BPEL processes based on an incomplete matchmaking semantics. Our algorithm performs in the worst case in polynomial time in the orders of the query graph and the process graph.

关键词： Query BPEL graph algorithm inexact matchmaking

来源：评论

学校读者我要写书评

暂无评论

Optimal Path Planning under Temporal Logic Constraints

Optimal Path Planning under Temporal Logic Constraints

引用

IEEE/RSJ International Conference on Intelligent Robots and Systems

作者： Smith, Stephen L. Tumova, Jana Belta, Calin Rus, Daniela MIT Comp Sci & Artificial Intelligence Lab 77 Massachusetts Ave Cambridge MA 02139 USA Boston Univ Dept Mech Engn Boston MA 02215 USA Masaryk Univ Fac Informat Brno Czech Republic

ISBN: (纸本)9781424466757

In this paper we present a method for automatically generating optimal robot trajectories satisfying high level mission specifications. The motion of the robot in the environment is modeled as a weighted transition system. The mission is specified by a general linear temporal logic formula. In addition, we require that an optimizing proposition must be repeatedly satisfied. The cost function that we seek to minimize is the maximum time between satisfying instances of the optimizing proposition. For every environment model, and for every formula, our method computes a robot trajectory which minimizes the cost function. The problem is motivated by robotic monitoring and data gathering. In this setting, the optimizing proposition is satisfied at locations where data can be uploaded, and the formula specifies a an infinite horizon data collection mission. Our method utilizes Buchi automata to produce an automaton (which can be thought of as a graph) whose runs satisfy the temporal logic formula. We then present a graph algorithm which computes a path corresponding to the optimal robot trajectory. We also present an implementation for a robot performing a data gathering mission.

关键词： Buchi automata automata theory data acquisition data gathering graph algorithm infinite horizon data collection mission motion control multi-robot systems optimal control optimal path planning optimal robot trajectories optimisation optimizing proposition path planning position control robot motion robotic monitoring temporal logic temporal logic constraints weighted transition system

来源：评论

学校读者我要写书评

暂无评论

Approximating capacitated tree-routings in networks

Approximating capacitated tree-routings in networks

引用

4th International Conference on Theory and Applications of Models of Computation

作者： Morsy, Ehab Nagamochi, Hiroshi Kyoto Univ Dept Appl Math & Phys Kyoto 6068501 Japan Yoshida Honmachi Kyoto 6068501 Japan

ISBN: (纸本)9783540725039

The capacitated tree-routing problem (CTR) in a graph G = (V, E) consists of an edge weight function w : E -> R+, a sink s is an element of V, a terminal set M subset of V with a demand function q : M -> R+, a routing capacity k > 0, and an integer edge capacity lambda >= 1. The CTR asks to find a partition M = {Z(1), Z(2), . . ., Z(l)} of M and a set T = {T-1, T-2, . . ., T-l} of trees of G such that each T-i spans Z(i) boolean OR {s} and satisfies Sigma(v is an element of Zi) q(v) <= k. A subset of trees in T can pass through a single copy of an edge e is an element of E as long as the number of these trees does not exceed the edge capacity lambda;any integer number of copies of e are allowed to be installed, where the cost of installing a copy of e is w(e). The objective is to find a solution (M, T) that minimizes the installing cost Sigma(e is an element of E) [vertical bar{T is an element of T vertical bar T contains e}vertical bar/lambda]w(e). In this paper, we propose a (2 + rho(ST))-approximation algorithm to the CTR, where rho(ST) is any approximation ratio achievable for the Steiner tree problem.

关键词： approximation algorithm graph algorithm routing problems network optimization tree cover

来源：评论

学校读者我要写书评

暂无评论

A Fast algorithm for Finding Dominators in a Flowgraph

引用

ACM Transactions on Programming Languages and Systems (TOPLAS) 1979年第1期1卷 121-141页

作者： Lengauer, Thomas Tarjan, Robert Endre Computer Science Department Stanford University Stanford CA 94305 United States

A fast algorithm for finding dominators in a flowgraph is presented. The algorithm uses depth-first search and an efficient method of computing functions defined on paths in trees. A simple implementation of the algorithm runs in O(m log n) time, where m is the number of edges and n is the number of vertices in the problem graph. A more sophisticated implementation runs in O(mα(m, n)) time, where α(m, n) is a functional inverse of Ackermann's *** versions of the algorithm were implemented in Algol W, a Stanford University version of Algol, and tested on an IBM 370/168. The programs were compared with an implementation by Purdom and Moore of a straightforward O(mn)-time algorithm, and with a bit vector algorithm described by Aho and Ullman. The fast algorithm beat the straightforward algorithm and the bit vector algorithm on all but the smallest graphs tested. © 1979, ACM. All rights reserved.

关键词： depth-first search dominators global flow analysis graph algorithm path compression

来源：评论

学校读者我要写书评

暂无评论

A study on the locality behavior of minimum spanning tree algorithms

引用

13th International Conference on High Performance Computing (HiPC 2006)

作者： Cong, Guojing Sbaraglia, Simone IBM Corp TJ Watson Res Ctr Yorktown Hts NY 10598 USA

ISBN: (纸本)9783540680390

Locality behavior study is crucial for achieving good performance for irregular problems. graph algorithms with large, sparse inputs, for example, often times achieve only a tiny fraction of the potential peak performance on current architectures. Compared with most numerical algorithms graph algorithms lay higher pressure on the memory system. In this paper, using the minimum spanning tree problem as an example, we study the locality behavior of graph algorithms, both sequential and parallel, for arbitrary, sparse instances. We show that the inherent locality of graph algorithms may not be favored by the current architecture, and parallel graph algorithms tend to have significantly poorer locality behaviors than their sequential counterparts. As memory hierarchy gets deeper and processors start to contain multi-cores, our study suggests that architectural support and new parallel algorithm designs are necessary for achieving good performance for irregular graph problems.

关键词： memory locality graph algorithm minimum spanning tree

来源：评论

学校读者我要写书评

暂无评论

On Breaking Truss-Based Communities 21

On Breaking Truss-Based Communities

引用

27th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)

作者： Chen, Huiping Conte, Alessio Grossi, Roberto Loukides, Grigorios Pissis, Solon P. Sweering, Michelle Kings Coll London London England Univ Pisa Pisa Italy CWI Amsterdam Netherlands Vrije Univ Amsterdam Netherlands

ISBN: (纸本)9781450383325

A k-truss is a graph such that each edge is contained in at least k - 2 triangles. This notion has attracted much attention, because it models meaningful cohesive subgraphs of a graph. We introduce the problem of identifying a smallest edge subset of a given graph whose removal makes the graph k-truss-free. We also introduce a problem variant where the identified subset contains only edges incident to a given set of nodes and ensures that these nodes are not contained in any k-truss. These problems are directly applicable in communication networks: the identified edges correspond to vital network connections;or in social networks: the identified edges can be hidden by users or sanitized from the output graph. We show that these problems are NP-hard. We thus develop exact exponential-time algorithms to solve them. To process large networks, we also develop heuristics sped up by an efficient data structure for updating the truss decomposition under edge deletions. We complement our heuristics with a lower bound on the size of an optimal solution to rigorously evaluate their effectiveness. Extensive experiments on 10 real-world graphs show that our heuristics are effective (close to the optimal or to the lower bound) and also efficient (up to two orders of magnitude faster than a natural baseline).

关键词： graph algorithm k-truss community detection

来源：评论

学校读者我要写书评

暂无评论

Efficient Maximal Balanced Clique Enumeration in Signed Networks 20

Efficient Maximal Balanced Clique Enumeration in Signed Netw...

引用

29th World Wide Web Conference (WWW)

作者： Chen, Zi Yuan, Long Lin, Xuemin Qin, Lu Yang, Jianye East China Normal Univ Shanghai Peoples R China Nanjing Univ Sci & Technol Nanjing Peoples R China Univ New South Wales Sydney NSW Australia Univ Technol Sydney Sydney NSW Australia Hunan Univ Changsha Peoples R China

ISBN: (纸本)9781450370233

Clique is one of the most fundamental models for cohesive subgraph mining in network analysis. Existing clique model mainly focuses on unsigned networks. In real world, however, many applications are modeled as signed networks with positive and negative edges. As the signed networks hold their own properties different from the unsigned networks, the existing clique model is inapplicable for the signed networks. Motivated by this, we propose the balanced clique model that considers the most fundamental and dominant theory, structural balance theory, for signed networks, and study the maximal balanced clique enumeration problem which computes all the maximal balanced cliques in a given signed network. We show that the maximal balanced clique enumeration problem is NP-Hard. A straightforward solution for the maximal balanced clique enumeration problem is to treat the signed network as two unsigned networks and leverage the off-the-shelf techniques for unsigned networks. However, such a solution is inefficient for large signed networks. To address this problem, in this paper, we first propose a new maximal balanced clique enumeration algorithm by exploiting the unique properties of signed networks. Based on the new proposed algorithm, we devise two optimization strategies to further improve the efficiency of the enumeration. We conduct extensive experiments on large real and synthetic datasets. The experimental results demonstrate the efficiency, effectiveness and scalability of our proposed algorithms.

关键词： Maximal Balanced Clique Signed Network graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Acyclic Matching in Some Subclasses of graphs 31st

Acyclic Matching in Some Subclasses of Graphs

引用

31st International Workshop on Combinatorial algorithms (IWOCA)

作者： Panda, B. S. Chaudhary, Juhi Indian Inst Technol Delhi Dept Math Comp Sci & Applicat Grp New Delhi 110016 India

ISBN: (纸本)9783030489656;9783030489663

A subset M subset of E of edges of a graph G = (V, E) is called a matching if no two edges of M share a common vertex. A matching M in a graph G is called an acyclic matching if G[V (M)], the subgraph of G induced by the M-saturated vertices of G is acyclic. The ACYCLIC MATCHING PROBLEM is the problem of finding an acyclic matching of maximum size. The decision version of the ACYCLIC MATCHING PROBLEM is known to be NP-complete for general graphs as well as for bipartite graphs. In this paper, we strengthen this result by showing that the decision version of the ACYCLIC MATCHING PROBLEM remains NP-complete for comb-convex bipartite graphs and dually-chordal graphs. On the positive side, we present linear time algorithms to compute an acyclic matching of maximum size in split graphs and proper interval graphs. Finally, we show that the ACYCLIC MATCHING PROBLEM is hard to approximate within a factor of n(1-epsilon) for any epsilon > 0, unless P = NP and the ACYCLIC MATCHING PROBLEM is APX-complete for 2k + 1-regular graphs for k >= 3, where k is a constant.

关键词： Matching Bipartite graphs Chordal graphs graph algorithm NP-completeness Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A variant of Snay's algorithm 37

A variant of Snay's algorithm

引用

37th International Conference of the Chilean-Computer-Science-Society (SCCC)

作者： Gonzaga de Oliveira, Sanderson L. Bernardes, Junior A. B. de Abreu, Alexandre A. A. M. Univ Fed Lavras Dept Ciencia Comp Lavras Brazil Inst Fed Educ Ciencia & Tecnol Santa Catarina Canoinhas Brazil

ISBN: (纸本)9781538692332

This paper presents a variant of Snay's algorithm for profile reduction of matrices. The new heuristic for profile reduction shows better results when compared with the results of several reordering algorithms with regards to reducing the computational cost of the zero-fill incomplete Cholesky-preconditioned conjugate gradient method applied to small linear systems arising from a computational fluid dynamics problem.

关键词： Sparse matrices reordering algorithms renumbering ordering graph labeling graph algorithm bandwidth reduction profile reduction numbering graph theory conjugate gradient method incomplete Cholesky factorization heat conduction equation

来源：评论

学校读者我要写书评

暂无评论

Fine-Tuning Decomposition Theorem for Maximum Weight Bipartite Matching

Fine-Tuning Decomposition Theorem for Maximum Weight Biparti...

引用

11th Annual Conference on Theory and Applications of Models of Computation (TAMC)

作者： Das, Shibsankar Kapoor, Kalpesh Indian Inst Technol Guwahati Dept Math Gauhati 781039 India

ISBN: (纸本)9783319060897;9783319060880

Let G be an undirected bipartite graph with non-negative integer weights on the edges. We refine the existing decomposition theorem originally proposed by Kao et al. in the context of maximum weight bipartite matching. We apply it to design an efficient version of the decomposition algorithm to compute the weight of a maximum weight bipartite matching of G in O(root nW'/k(n, W'/m'))-time by employing an algorithm designed by Feder and Motwani as a subroutine, where n, m, m' (<= m) denote number of nodes, number of edges and number of distinct edge weights of G, respectively. The parameter W' is smaller than the total edge weight W, essentially when the largest edge weight differs by more than one from the second largest edge weight in the current working graph in decomposition step of the algorithm. In best case W' = O(m) and in worst case W' = W, i.e., m <= W' <= W.

关键词： graph algorithm maximum weight bipartite matching graph decomposition minimum weight vertex cover

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：