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

IEEE 29th Conference on Computational Complexity (CCC)

作者： Goebel, Andreas Goldberg, Leslie Ann McQuillan, Colin Richerby, David Yamakami, Tomoyuki Univ Oxford Oxford OX1 2JD England Univ Liverpool Liverpool Merseyside England Univ Fukui Fukui Japan

ISBN: (纸本)9781479936267

Given a symmetric D x D matrix M over {0, 1, *}, a list M/partition of a graph G is a partition of the vertices of G into D parts which are associated with the rows of M. The part of each vertex is chosen from a given list in such a way that no edge of G is mapped to a 0 in M and no non-edge of G is mapped to a 1 in M. Many important graph-theoretic structures can be represented as list M-partitions including graph colourings, split graphs and homogeneous sets, which arise in the proofs of the weak and strong perfect graph conjectures. Thus, there has been quite a bit of work on determining for which matrices M computations involving list M-partitions are tractable. This paper focuses on the problem of counting list M-partitions, given a graph G and given lists for each vertex of G. We give an algorithm that solves this problem in polynomial time for every (fixed) matrix M for which the problem is tractable. The algorithm relies on data structures such as sparse-dense partitions and subcube decompositions to reduce each problem instance to a sequence of problem instances in which the lists have a certain useful structure that restricts access to portions of M in which the interactions of 0s and 1s is controlled. We show how to solve the resulting restricted instances by converting them into particular counting constraint satisfaction problems (#CSPs) which we show how to solve using a constraint satisfaction technique known as "arc-consistency". For every matrix M for which our algorithm fails, we show that the problem of counting list M-partitions is #P-complete. Furthermore, we give an explicit characterisation of the dichotomy theorem - counting list M-partitions is tractable (in FP) if and only if the matrix M has a structure called a derectangularising sequence. Finally, we show that the meta-problem of determining whether a given matrix has a derectangularising sequence is NP-complete.

关键词： Complexity theory Data structures Educational institutions Europe Partitioning algorithms Standards Symmetric matrices counting complexity dichotomy theorem graph algorithms graph homomorphism Partitioning algorithms Data structures Symmetric matrix Complexity theory graph algorithms Educational institutions MOMENT MAGNITUDE matrices

来源：评论

学校读者我要写书评

暂无评论

Applying MapReduce principle to High level information fusion 17

Applying MapReduce principle to High level information fusio...

引用

17th International Conference on Information Fusion (FUSION)

作者： Laudy, Claire Dreo, Johann Gouguenheim, Christophe Thales Research &amp Technology

ISBN: (纸本)9781479916344

The InSyTo Synthesis framework is based on graph structures, graph algorithms and similarity measures for soft data fusion managing inconsistencies. The framework can be used to enable non-redundant additions to an information network, as well as graph based information query on several applications. The graph fusion algorithm relies on the search of a maximum common subgraph isomorphism, which makes it a difficult problem, especially on large graphs. In this work, the subgraph matching algorithm is partially parallelized, based on the Map Reduce approach and on the Hadoop framework. Using Hadoop enables the management of big graphs, first by avoiding the load of the graphs in memory and secondly by distributing the computations over several processing nodes. Our experiments on the Global Terrorism Database (which contains the descriptions of more than 113,000 terrorist attacks in a graph of more than 20,000,000 nodes) shows that InSyTo Synthesis now scales to so-called "big data" applications.

关键词： Big data Context Data integration Data models Semantics Terrorism Vocabulary data integration Terrorism big data data models Semantics Information fusion Vocabulary Information Network Line graph semiotics graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Hybrid BFS Approach Using Semi-External Memory 28

Hybrid BFS Approach Using Semi-External Memory

引用

28th IEEE International Parallel & Distributed Processing Symposium Workshops (IPDPSW)

作者： Iwabuchi, Keita Sato, Hitoshi Mizote, Ryo Yasui, Yuichiro Fujisawa, Katsuki Matsuoka, Satoshi Tokyo Inst Technol Tokyo Japan Chuo Univ Tokyo Japan Japan Sci & Technol Agcy Kawaguchi Saitama Japan

ISBN: (纸本)9781479941162

NVM devices will greatly expand the possibility of processing extremely large-scale graphs that exceed the DRAM capacity of the nodes;however, efficient implementation based on detailed performance analysis of access patterns of unstructured graph kernel on systems that utilize a mixture of DRAM and NVM devices has not been well investigated. We introduce a graph data offloading technique using NVMs that augment the hybrid BFS (Breadth-first search) algorithm widely used in the graph500 benchmark, and conduct performance analysis to demonstrate the utility of NVMs for unstructured data. Experimental results of a Scale27 problem of a Kronecker graph with 2(27) vertices and 2(31) edges compliant to the graph500 benchmark show that our approach maximally sustains 4.22 Giga TEPS (Traversed Edges Per Second), reducing DRAM size by half with only 19.18% performance degradation on a 4-way AMD Opteron 6172 machine heavily equipped with NVM devices. Although direct comparison is difficult, this is significantly greater than the result of 0.05 GTEPS for a SCALE 36 problem by using 1TB of DRAM and 12 TB of NVM as reported by Pearce et al. [1] Although our approach uses higher DRAM to NVM ratio, we show that a good compromise is achievable between performance vs. capacity ratio for processing large-scale graphs. This result as well as detailed performance analysis of the proposed technique suggests that we can process extremely large-scale graphs per node with minimum performance degradation by carefully considering the data structures of a given graph and the access patterns to both DRAM and NVM devices. As a result, our implementation has achieved 4.35 MTEPS/W(Mega TEPS per Watt) and ranked 4th on November 2013 edition of the Green graph500 list in the Big Data category [2] by using only a single fat server heavily equipped with NVMs.

关键词： Breadth-first search graph algorithms NVM Memory architecture Extreme Big Data

来源：评论

学校读者我要写书评

暂无评论

Modeling spatial compositions with network-based spaced layouts

Modeling spatial compositions with network-based spaced layo...

引用

2014 International Conference on Computing in Civil and Building Engineering

作者： Suter, G. Design Computing Group Faculty of Architecture and Planning Vienna University of Technology Treitlstrasse 3 Vienna Austria

ISBN: (纸本)9780784413616

A significant challenge in building information modeling (BIM) concerns support for modeling multiple views of buildings to meet diverse data needs of architectural, structural, or building services domains. The focus in this paper is on extending an existing schema for network-based space layouts with spatial composition modeling capabilities. The schema has been introduced in previous work to support modeling of multiple space views. Network-based space layouts are generated from space data that are created in BIM authoring systems. Selected, view-specific, spatial relations between objects in a layout are modeled as a spatial relation network. An architectural designer may use graph algorithms to find the shortest path in the spatial relation network of a pedestrian circulation layout between a workplace and a building exit. Likewise, a lighting control system designer may query a spatial relation network of a lighting layout to determine luminaires that are near a workplace. Multi-view space models may be composed of layouts with view-specific spatial relation networks. However, spatial compositions are currently not modeled explicitly. The schema is, therefore, extended with topological spatial relations which include: containment, overlap, equality, touch, and disjoint relations. With these relations, it is feasible to relate objects in different layouts. They are derived from object geometries with clash classification functions that are provided by a commercial solid modeling engine. Examples from pedestrian circulation and lighting domains illustrate rich spatial composition of network-based space layouts and their benefits for building design. © ASCE 2014.

关键词： layouts spatial composition Modeling Buildings Workplace graph algorithms schema shortest path dimensional relationship

来源：评论

学校读者我要写书评

暂无评论

Puzzles as Excellent Tool Supporting graph Problems Understanding

引用

Procedia - Social and Behavioral Sciences 2014年 131卷 177-181页

作者： Eva Milková Eva Milková University of Hradec Kralove Rokitanského 62 Hradec Kralove 500 03 Czech Republic

The main aim of the subjects dealing with graph theory and combinatorial optimization is to develop and deepen students’ capacity for logical and algorithmic thinking. Usually, after learning of basic graph concepts students are introduced to more complex algorithms with a polynomial time complexity at first. On the one hand, usually, there are more methods, which can be used for solving the same graph-problem, while on the other hand, using effective modifications of one algorithm, methods of solving various other tasks can be devised. To engage students to the subject a particular problem with a real life example or puzzle is introduced as a prototype of the explained concept or algorithm and suitable graph-representation of a problem is discussed. In the paper we devote attention to the role of puzzles as a useful study material supporting understanding of graph algorithms. On a case study we introduce puzzles, going from a simple to more complex one, as an appropriate Breadth-First- Search algorithm background. The aim of the paper is to introduce our approach that can serve to pedagogues as good inspiration to their teaching.

关键词： Puzzle prototype graph theory graph problems graph algorithms BFS algorithm

来源：评论

学校读者我要写书评

暂无评论

AUTOMATED LAYOUT OF PROCESS DESCRIPTION MAPS DRAWN IN SYSTEMS BIOLOGY graphICAL NOTATION

AUTOMATED LAYOUT OF PROCESS DESCRIPTION MAPS DRAWN IN SYSTEM...

引用

作者： Begum Genc Bilkent University

学位级别：硕士

Evolving technology has increased the focus on genomics. The combination of today's advanced studies with decades of molecular biology research yield in huge amount of pathway data. These models can be used to improve high-throughput data analysis by linking correlation to the causation, shedding light on many complex diseases. In order to prevent ambiguity and ensure regularity of the research, a need for using a standard notation has emerged. Systems Biology graphical Notation (SBGN) is a visual language developed by a community of biochemists, modellers and computer scientists with the intention of enabling scientists to represent networks, including models of cellular processes, in a standard, unambiguous way. SBGN is formed of three languages: process, entity relationship and activity flow. This research is focused on its process diagram branch. Automated layout is commonly used to clearly visualize the information repre- sented by graphs. Considering the fact that, biological pathways includes nested structures (e. g., nucleoplasms), we have made use of a force-directed automatic layout algorithm called Compound Spring Embedder (CoSE), which supports the compound graph structures. On top of this layout structure, we have developed a specialized layout algorithm called SBGN-PD layout. SBGN-PD layout enhancements mainly include properly tiling of complex members and disconnected molecules, placement of product and substrate edges on the opposite sides of a process node without disturbing the force-directed structure of the algorithm.

关键词： information visualization graph layout automatic layout biological networks biological process diagrams graph algorithms graph visualization systems biology graphical notation compound spring embedder

来源：评论

学校读者我要写书评

暂无评论

graph-based algorithms for Text Summarization

Graph-based algorithms for Text Summarization

引用

International Conference on Emerging Trends in Engineering and Technology

作者： Thakkar, Khushboo S. Dharaskar, R.V. Chandak, M.B. Department of Computer Science and Engineering G. H. Raisoni College of Engineering Nagpur India Dept. of Computer Science and Engineering Shri Ramdeobaba Kamla Nehru Engineering College Nagpur India

ISBN: (纸本)9780769542461

Summarization is a brief and accurate representation of input text such that the output covers the most important concepts of the source in a condensed manner. Text Summarization is an emerging technique for understanding the main purpose of any kind of documents. To visualize a large text document within a short duration and small visible area like PDA screen, summarization provides a greater flexibility and convenience. This paper presents innovative unsupervised methods for automatic sentence extraction using graph-based ranking algorithms and shortest path algorithm. © 2010 IEEE.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

graph matching and clustering using kernel attributes

引用

NEUROCOMPUTING 2013年 113卷 177-194页

作者： Angel Lozano, Miguel Escolano, Francisco Univ Alicante Dept Ciencia Comp & Inteligencia Artificial Alicante Spain

In this paper, we exploit graph kernels for graph matching and clustering. Firstly, we analyze different kinds of graph kernels in order to extract from them attributes to be used as a similarity measure between nodes of non-attributed graphs. Next, such attributes are embedded in a graph-matching cost function, through a probabilistic framework, and we evaluate their performance within a graph-matching algorithm. Secondly, we propose a method for obtaining a representative prototype from a set of graphs, which relies on obtaining all the pairwise matchings between the input graphs, and uses the information provided by graph kernels in order to select the matchings that will be considered for obtaining the prototype. Nodes and edges in such a prototype graph register their frequency of occurrence, so that it can be considered a first-order generative model. The proposed method for building prototypes is efficiently integrated into a central clustering algorithm, which allows us to unsupervisedly learn the class-structure of a given set of graphs, and the prototypes representing each class, thus obtaining a central graph clustering algorithm with the same computational cost than a pairwise one. We successfully apply the proposed methods to structural recognition problems. (C) 2013 Elsevier B.V. All rights reserved.

关键词： graph algorithms Pattern matching Clustering Computer vision

来源：评论

学校读者我要写书评

暂无评论

Revisit of Erdos-Gallai's theorem on the circumference of a graph

引用

INFORMATION PROCESSING LETTERS 2013年第17期113卷 646-648页

作者： Fujita, Shinya Lesniak, Linda Maebashi Inst Technol Dept Integrated Design Engn Maebashi Gunma 3710816 Japan Drew Univ Dept Math & Comp Sci Madison NJ 07940 USA Western Michigan Univ Dept Math Kalamazoo MI 49008 USA

Let c, m, n be integers with n >= c >= 3, and let G be a graph of order n with m edges. A classical theorem by Eras and Gallai states that if m > (c - 1)(n - 1)/2, then G contains a cycle of order at least c. In fact, the bound on m in this theorem is not sharp when both n and c are even. In this work we give the sharp value for this case. (C) 2013 Elsevier B.V. All rights reserved.

关键词： graph algorithms Circumference Cycle Maximum number of edges

来源：评论

学校读者我要写书评

暂无评论

From "Think Like a Vertex" to "Think Like a graph"

引用

PROCEEDINGS OF THE VLDB ENDOWMENT 2013年第3期7卷 193-204页

作者： Tian, Yuanyuan Balmin, Andrey Corsten, Severin Andreas Tatikonda, Shirish McPherson, John IBM Almaden Res Ctr Yorktown Hts NY 10598 USA GraphSQL Redwood City CA 94065 USA IBM Deutschland GmbH Berlin Germany

To meet the challenge of processing rapidly growing graph and network data created by modern applications, a number of distributed graph processing systems have emerged, such as Pregel and graphLab. All these systems divide input graphs into partitions, and employ a "think like a vertex" programming model to support iterative graph computation. This vertex-centric model is easy to program and has been proved useful for many graph algorithms. However, this model hides the partitioning information from the users, thus prevents many algorithm-specific optimizations. This often results in longer execution time due to excessive network messages (e.g. in Pregel) or heavy scheduling overhead to ensure data consistency (e.g. in graphLab). To address this limitation, we propose a new "think like a graph" programming paradigm. Under this graph-centric model, the partition structure is opened up to the users, and can be utilized so that communication within a partition can bypass the heavy message passing or scheduling machinery. We implemented this model in a new system, called Giraph++, based on Apache Giraph, an open source implementation of Pregel. We explore the applicability of the graph-centric model to three categories of graph algorithms, and demonstrate its flexibility and superior performance, especially on well-partitioned data. For example, on a web graph with 118 million vertices and 855 million edges, the graph-centric version of connected component detection algorithm runs 63X faster and uses 204X fewer network messages than its vertex- centric counterpart.

关键词： graph theory Iterative methods Machinery Message passing Open source software Open systems Scheduling Connected component graph algorithms graph computations Modern applications Open source implementation Partition structures Programming models Programming paradigms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：