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

A constraint graph representation of metamorphic linkages

MECHANISM AND MACHINE THEORY 2011年第2期46卷 228-238页

作者： Li, Duanling Zhang, Zhonghai McCarthy, J. Michael Beijing Univ Posts & Telecommun Automat Sch Beijing 100088 Peoples R China Univ Calif Irvine Robot & Automat Lab Irvine CA 92697 USA

A metamorphic linkage has the property that the effective number of links and joints can change during the movement of the device. This means the kinematic structural representation of a metamorphic linkage has different forms in which vertices and edges combine depending on the configuration of the device. In this paper, we use the constraint graph of computational geometry rather than the traditional topological graph to characterize a metamorphic linkage in order to simplify the representation of its configuration changes. A constraint graph has geometric elements as vertices and their relationships as edges. We find that the adjacency sub matrix of the constraint graph provides a convenient description of changes in the topology of links and joints in the operation of the metamorphic linkage. Operations on the adjacency submatrix capture topological changes in a metamorphic linkage. We illustrate our results with several examples. (C) 2010 Elsevier Ltd. All rights reserved.

关键词： Metamorphic mechanisms Configuration changes constraint graph Adjacency sub-matrix

来源：评论

学校读者我要写书评

暂无评论

RANKING VALID TOPOLOGIES OF THE SECONDARY STRUCTURE ELEMENTS USING A constraint graph

引用

JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY 2011年第3期9卷 415-430页

作者： Al Nasr, Kamal Ranjan, Desh Zubair, Mohammad He, Jing Old Dominion Univ Dept Comp Sci Norfolk VA 23529 USA

Electron cryo-microscopy is a fast advancing biophysical technique to derive three-dimensional structures of large protein complexes. Using this technique, many density maps have been generated at intermediate resolution such as 6-10 angstrom resolution. Although it is challenging to derive the backbone of the protein directly from such density maps, secondary structure elements such as helices and beta-sheets can be computationally detected. Our work in this paper provides an approach to enumerate the top-ranked possible topologies instead of enumerating the entire population of the topologies. This approach is particularly practical for large proteins. We developed a directed weighted graph, the topology graph, to represent the secondary structure assignment problem. We prove that the problem of finding the valid topology with the minimum cost is NP hard. We developed an O(N(2)2(N)) dynamic programming algorithm to identify the topology with the minimum cost. The test of 15 proteins suggests that our dynamic programming approach is feasible to work with proteins of much larger size than we could before. The largest protein in the test contains 18 helical sticks detected from the density map out of 33 helices in the protein.

关键词： constraint graph topology secondary structure shortest path electron cryomicroscopy

来源：评论

学校读者我要写书评

暂无评论

Exploiting the Structure of the constraint graph for Efficient Points-to Analysis 12

Exploiting the Structure of the Constraint Graph for Efficie...

引用

2012 International Symposium on Memory Management

作者： Nasre, Rupesh Indian Inst Sci Bangalore 560012 Karnataka India Univ Texas Austin Austin TX USA

ISBN: (纸本)9781450313506

Points-to analysis is a key compiler analysis. Several memory related optimizations use points-to information to improve their effectiveness. Points-to analysis is performed by building a constraint graph of pointer variables and dynamically updating it to propagate more and more points-to information across its subset edges. So far, the structure of the constraint graph has been only trivially exploited for efficient propagation of information, e.g., in identifying cyclic components or to propagate information in topological order. We perform a careful study of its structure and propose a new inclusion-based flow-insensitive context-sensitive points-to analysis algorithm based on the notion of dominant pointers. We also propose a new kind of pointer-equivalence based on dominant pointers which provides significantly more opportunities for reducing the number of pointers tracked during the analysis. Based on this hitherto unexplored form of pointer-equivalence, we develop a new context-sensitive flow-insensitive points-to analysis algorithm which uses incremental dominator update to efficiently compute points-to information. Using a large suite of programs consisting of SPEC 2000 benchmarks and five large open source programs we show that our points-to analysis is 88% faster than BDD-based Lazy Cycle Detection and 2x faster than Deep Propagation. We argue that our approach of detecting dominator-based pointer-equivalence is a key to improve points-to analysis efficiency.

关键词： Algorithms Languages constraint graph dominators points-to analysis context-sensitivity

来源：评论

学校读者我要写书评

暂无评论

Push-Pull constraint graph for Efficient Points-to Analysis

引用

ACM SIGPLAN NOTICES 2014年第11期49卷 25-33页

作者： Ratnakar, Bollu Nasre, Rupesh IIT Madras Tamil Nadu India

We present techniques for efficient computation of points-to information for C programs. Pointer analysis is an important phase in the compilation process. The computed points-to information and the alias information is useful for client analyses from varied domains such as bug finding, data-flow analysis, identifying security vulnerabilities, and parallelization, to name a few. Former research on pointer analysis has indicated that the main bottleneck towards scalability is manifested by the presence of complex constraints (load p = *q and store *p = q constraints) in the program. Complex constraints add edges to the constraint graph in an unpredictable manner and are responsible for initiating propagation of large amounts of points-to information across edges. We identify that the root cause to this issue is in the homogeneous structure in the constraint graph, due to which existing analyses treat loads and stores in a uniform manner. To address these issues, we present two techniques. First, we represent a constraint graph in a non-homogeneous manner, treat loads and stores in different ways, and employ a push-pull model for non-uniform propagation. Second, we propose lazy propagation which propagates information in the constraint graph only when necessary. We illustrate the effectiveness of our techniques using six large open-source programs and show that they improve the analysis time over a state-of-the-art BDD-based analysis by 33% and over Deep Propagation by 21%.

关键词： Algorithms Languages constraint graph points-to analysis push-pull lazy propagation propagation patterns

来源：评论

学校读者我要写书评

暂无评论

A new Algorithm for the Solution of under constraint graph in Sketch Drawing

引用

Computer Aided Drafting,Design and Manufacturing 2001年第1期11卷 26-32页

作者： Dong Yude①② Zhao Han② Tang Jianrong③ ① Department of Computer, University of Science and Technology of China, Hefei 230052, China ② Hefei University of Technology, Hefei 230009, China ③State Key Lab. of CAD&CG, ZheJiang University, Hangzhou Department of Computer University of Science and Technology of China Hefei 230052 China Hefei University of Technology Hefei 230009 China Hefei University of Technology Hefei 230009 China State Key Lab. of CAD&CG ZheJiang University Hangzhou 310027 China

A new algorithm for the solution of under constraint graph in sketch drawing is put forward. The directed process of constraint graph is completed by picking concealed constraints of adjacent entities in sketch of few or no dimensions. In this paper, the priority of concealed constraint is given by the different constraint types and constructing orders, and some more priority concealed constraints are forced into obvious ones by the need number of constraint for every node in constraint solution process.

关键词： under constraint constraint graph directed constraint graph

来源：评论

学校读者我要写书评

暂无评论

OPERATIONAL VARIABLE JOB SCHEDULING WITH ELIGIBILITY constraintS: A RANDOMIZED constraint-graph-BASED APPROACH

引用

TECHNOLOGICAL AND ECONOMIC DEVELOPMENT OF ECONOMY 2009年第2期15卷 245-266页

作者： Eliiyi, Deniz Tuersel Korkmaz, Aslihan Gizem Cicek, Abdullah Ercuement Izmir Univ Econ TR-35330 Izmir Turkey Sabanci Univ TR-34956 Istanbul Turkey

In this study, we consider the problem of Operational Variable Job Scheduling, also referred to as parallel machine scheduling with time windows. The problem is a more general version of the Fixed Job Scheduling problem, involving a Lime window for each job larger than its processing time. The objective is to find the optimal subset of the jobs that can be processed. An interesting application area ties in Optimal Berth Allocation, which involves the assignment of vessels arriving at the port to appropriate berths within their time windows, while maximizing the total profit from the served vessels. Eligibility constraints are also taken into consideration. We develop an integer programming model for the problem. We show that the problem is NP-hard, and develop a constraint-graph-based construction algorithm for generating near-optimal solutions. We use genetic algorithm and other improvement algorithms to enhance the solution. Computational experimentation reveals that our algorithm generates very high quality solutions in very small computation times.

关键词： operational variable job scheduling eligibility constraints optimal berth allocation genetic algorithm constraint satisfaction constraint graph

来源：评论

学校读者我要写书评

暂无评论

A constraint Dynamic graph Approach to identify the Secondary Structure Topology from cryoEM Density Data in Presence of Errors

A Constraint Dynamic Graph Approach to identify the Secondar...

引用

IEEE International Conference on Bioinformatics and Biomedicine (BIBM)

作者： Biswas, Abhishek Si, Dong Al Nasr, Kamal Ranjan, Desh Zubair, Mohammad He, Jing Old Dominion Univ Dept Comp Sci Norfolk VA 23529 USA

ISBN: (纸本)9780769545745

The determination of the secondary structure topology is a critical step in deriving the atomic structure from the protein density map obtained from electron cryo-microscopy technique. This step often relies on the matching of two sources of information. One source comes from the secondary structures detected from the protein density map at the medium resolution, such as 5-10 angstrom. The other source comes from the predicted secondary structures from the amino acid sequence. Due to the uncertainty in either source of information, a pool of possible secondary structure positions has to be sampled in order to include the true answer. A naive way to find the native topology is to exhaustively map the pool of possible secondary structures detected in the density map with the pool of the secondary structures predicted from the sequence and search for the topology with the lowest cost. This paper studies the question that is how to reduce the computation of the mapping when the uncertainty of the secondary structure predictions is considered. We present a method that combines the concept of dynamic graph with our previous work of using constrained shortest path to identify the topology of the secondary structures. We show a reduction of about 34.55% time as comparison to the naive way of handling the inaccuracies. To our knowledge, this is the 1st computationally effective exact algorithm to identify the optimal topology of the secondary structures when the inaccuracy of the predicted data is considered.

关键词： constraint graph Dynamic graph Electron cryo-microscopy K-shortest path Protein Topology

来源：评论

学校读者我要写书评

暂无评论

Parametric Pattern-Making Modeling Based on constraint and graph

Parametric Pattern-Making Modeling Based on Constraint and G...

引用

Workshop on Intelligent Systems and Applications

作者： Yi Xiu Zhen-Kai Wan Wen-li Cao College of Computer Technology and Automation Tianjin Polytechnic University Computer Information Center Beijing Institute of Fashion Technology College of Computer Technology and Automation Tianjin Polytechnic University Computer Information Center Beijing Institute of Fashion Technology

ISBN: (纸本)9781424458721;9781424458745

Parametric pattern-making technology has based on procedural process for past decades in the field of GCAD. This paper presents a new method of parametric pattern-making technology. This method firstly finds out the constraint relations among geometric entities by analyzing the rules and sequences of geometric entities in pattern-making operation and confirms the local and whole well-constraint in pattern with geometric constraint principle, secondly represents the geometric constraints in pattern as a constraint graph and depicts the data structure of constraint graph with adjacent table, finally builds a parametric pattern-making model. The solving algorithm of the model implements the entity-edited and size-driven function. The experiments show the model is feasible and effective.

关键词： Geometric constraint constraint graph Parametric pattern-making Garment CAD

来源：评论

学校读者我要写书评

暂无评论

Checking of timing constraint violation based on graph in reactive systems

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2002年第4期E85A卷 909-913页

作者： Kobayashi, H Tokai Univ Detp Informat Med Technol Hiratsuka Kanagawa 2591292 Japan

The detection of tinting constraint violation is crucial in reactive systems. A method of detecting deadline violation based on Floyd-Warshall shortest path algorithm has been proposed by Chudrow et al. We extend this method to detect the violation of minimum delay time in reactive systems where the repetition of event sequences frequently occurs.

关键词： timing constraint violation constraint graph Rea Time Logic Floyd-Warshall algorithm

来源：评论

学校读者我要写书评

暂无评论

Fujimaki-Takahashi squeeze: Linear time construction of constraint graphs of floorplan for a given permutation

Fujimaki-Takahashi squeeze: Linear time construction of cons...

引用

20th Workshop on Circuits and Systems

作者： Takahashi, Toshihiko Fujimaki, Ryo Niigata Univ Grad Sch Sci & Technol Niigata 9502181 Japan

A floorplan is a subdivision of a rectangle into rectangular faces with horizontal and vertical line segments. We call a floorplan room-to-room when adjacencies between rooms are considered. Fujimaki and Takahashi showed that any room-to-room floorplan can be represented as a permutation. In this paper, we give an O(n)-time algorithm that constructs the vertical and the horizontal constraint graphs of a floorplan for a given permutation under this representation.

关键词： floorplan representation permutation constraint graph

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：