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

Colorful Frontier-Based Search: Implicit Enumeration of Chordal and Interval Subgraphs 1

Conference on Analysis of Experimental algorithms (SEA2)

作者： Kawahara, Jun Saitoh, Toshiki Suzuki, Hirofumi Yoshinaka, Ryo Nara Inst Sci & Technol Ikoma Japan Kyushu Inst Technol Iizuka Fukuoka Japan Hokkaido Univ Sapporo Hokkaido Japan Tohoku Univ Sendai Miyagi Japan

ISBN: (数字)9783030340292

ISBN: (纸本)9783030340292;9783030340285

This paper considers enumeration of specific subgraphs of a given graph by using a data structure called a zero-suppressed binary decision diagram (ZDD). A ZDD can represent the set of solutions quite compactly. Recent studies have demonstrated that a technique generically called frontier-based search (FBS) is a powerful framework for using ZDDs to enumerate various yet rather simple types of subgraphs. We in this paper, propose colorful FBS, an enhancement of FBS, which enables us to enumerate more complex types of subgraphs than existing FBS techniques do. On the basis of colorful FBS, we design methods that construct ZDDs representing the sets of chordal and interval subgraphs from an input graph. Computer experiments show that the proposed methods run faster than reverse search based algorithms.

关键词： graph algorithm graph enumeration Decision diagram Frontier-based search Interval graph Chordal graph

来源：评论

学校读者我要写书评

暂无评论

Computing the Metric Dimension by Decomposing graphs into Extended Biconnected Components (Extended Abstract) 13th

Computing the Metric Dimension by Decomposing Graphs into Ex...

引用

13th International Conference on algorithms and Computation (WALCOM)

作者： Vietz, Duygu Hoffmann, Stefan Wanke, Egon Heinrich Heine Univ Duesseldorf Univ Str 1 D-40225 Dusseldorf Germany

ISBN: (纸本)9783030105648;9783030105631

A vertex set U C V of an undirected graph G = (V, E) is a resolving set for G, if for every two distinct vertices u, v E V there is a vertex w E U such that the distance between u and w and the distance between v and w are different. The Metric Dimension of G is the size of a smallest resolving set for G. Deciding whether a given graph G has Metric Dimension at most k for some integer k is well-known to be NP-complete. A lot of research has been done to understand the complexity of this problem on restricted graph classes. In this paper, we decompose a graph into its so called extended biconnected components and present an efficient algorithm for computing the metric dimension for a class of graphs having a minimum resolving set with a bounded number of vertices in every extended biconnected component. Furthermore, we show that the decision problem METRIC DIMENSION remains NP-complete when the above limitation is extended to usual biconnected components.

关键词： graph algorithm Complexity Metric dimension Resolving set Biconnected component

来源：评论

学校读者我要写书评

暂无评论

Deep neural network model construction with interactive code reuse and automatic code transformation

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2020年第18期32卷 e5480-e5480页

作者： Lee, Keon Myung Park, Ki-Sun Hwang, Kyung-Soon Kim, Kwang-Il Chungbuk Natl Univ Dept Comp Sci Cheongju 28644 Chungbuk South Korea Police Jeju Natl Univ Dept Marine Ind & Maritime Jeju South Korea

Many application developers have been recently interested in applying deep learning techniques to their works but have little knowledge and experience on them. This paper presents the methods for a GUI-based modeling tool to easily build deep learning models and automatically transform them into executable program codes. For reuse of existing deep learning codes, it introduces a method that imports such a program code, extracts the deep learning model architecture, and transforms it into a graphical representation that can be modified on a graphical interface. Meanwhile, a deep learning model with many layers is difficult to be visualized on a small display screen. To handle the difficulty, it proposes a method to identify the submodules called articulable subgraphs in a deep learning model and to organize the deep learning model into a hierarchical architecture using the nesting relationships of articulable subgraphs. It introduces a method to identify frequent substractures as well as articulable subgraphs as building blocks for deep learning models for levelwise views. The hierarchical representation easily enables to build deep learning models with many layers. The GUI-based modeling tool employing the proposed methods makes nonexpert developers easily use deep learning techniques in their practical applications.

关键词： code generation deep learning deep neural network modeling graph algorithm machine learning

来源：评论

学校读者我要写书评

暂无评论

A Two-Player Coalition Cooperative Scheme for the Bodyguard Allocation Problem

引用

Journal of Computer Science & Technology 2018年第4期33卷 823-837页

作者： Jose Alberto Fernandez-Zepedu Daniel Brubeck-Salcedo Daniel Fajardo-Delgado Hector Zatarain-Aceves Department of Computer Science Center for Scientific Research and Higher Education of Ensenada Ensenada BC 22860 Mexico Department of Systems and Computation Instituto Technol6gico de Ciudad Guzmdn Guzmdn JAL 49100 Mexico

We address the bodyguard allocation problem （BAP）, an optimization problem that illustrates the conflict of interest between two classes of processes with contradictory preferences within a distributed system. While a class of processes prefers to minimize its distance to a particular process called the root, the other class prefers to maximize it; at the same time, all the processes seek to build a communication spanning tree with the maximum social welfare. The two state-of-the-art algorithms for this problem always guarantee the generation of a spanning tree that satisfies a condition of Nash equilibrium in the system; however, such a tree does not necessarily produce the maximum social welfare. In this paper, we propose a two-player coalition cooperative scheme for BAP, which allows some processes to perturb or break a Nash equilibrium to find another one with a better social welfare. By using this cooperative scheme, we propose a new algorithm called FFC-BAPs for BAP. We present both theoretical and empirical analyses which show that this algorithm produces better quality approximate solutions than former algorithms for BAP.

关键词： bodyguard allocation problem coalitional game graph algorithm Nash equilibrium

来源：评论

学校读者我要写书评

暂无评论

Distributed Triangle Counting algorithms in Simple graph Stream

Distributed Triangle Counting Algorithms in Simple Graph Str...

引用

International Conference on Parallel and Distributed Systems (ICPADS)

作者： Mengdi Yu Chao Song Jiqing Gu Ming Liu School of Computer Science and Engineering University of Electronic Science and Technology of China CHINA Big Data Research Center University of Electronic Science and Technology of China CHINA

ISBN: (纸本)9781728125848

Recently, the counting algorithm of local topology structures, such as triangles, has been widely used in social network analysis, recommendation systems, user portraits and other fields. At present, one-pass streaming algorithm for counting global and local triangles has been widely studied, and most researches focus on the single-machine streaming algorithm in a 'offline+batch processing' mode. However, researches on distributed online algorithm on multiple machines are still in its infancy, and this stage has not been thoroughly studied. In this paper, we investigate the triangle counting problem in large-scale simple undirected graphs whose edges arrive as a stream. We propose two distributed online streaming algorithms to estimate the global number of triangles, which are based on the current best performance sampling-based streaming algorithm. We mainly realize the reasonable partition of the graph stream, so that each worker independently estimates the number of triangles in a subgraph of the graph stream. Experimental results show that our algorithms reduce the estimation error and are several times more accurate than state-of-the-art streaming algorithms.

关键词： Approximate algorithm Distributed streaming algorithm graph algorithm graph stream Triangle counting algorithm Triangle graph algorithms algorithms Streaming streams Line graph

来源：评论

学校读者我要写书评

暂无评论

Sparse Hardware Embedding of Spiking Neuron Systems for Community Detection

引用

ACM JOURNAL ON EMERGING TECHNOLOGIES IN COMPUTING SYSTEMS 2018年第4期14卷 1–13页

作者： Hamilton, Kathleen E. Imam, Neena Humble, Travis S. Oak Ridge Natl Lab One Bethel Valley Rd Oak Ridge TN 37831 USA

We study the applicability of spiking neural networks and neuromorphic hardware for solving general optimization problems without the use of adaptive training or learning algorithms. We leverage the dynamics of Hopfield networks and spin-glass systems to construct a fully connected spiking neural system to generate synchronous spike responses indicative of the underlying community structure in an undirected, unweighted graph. Mapping this fully connected system to current generation neuromorphic hardware is done by embedding sparse tree graphs to generate only the leading-order spiking dynamics. We demonstrate that for a chosen set of benchmark graphs, the spike responses generated on a current generation neuromorphic processor can improve the stability of graph partitions and non-overlapping communities can be identified even with the loss of higher-order spiking behavior if the graphs are sufficiently dense. For sparse graphs, the loss of higher-order spiking behavior improves the stability of certain graph partitions but does not retrieve the known community memberships.

关键词： Optimization community detection neural network graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Enumerating All Spanning Shortest Path Forests with Distance and Capacity Constraints

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2018年第9期E101A卷 1363-1374页

作者： Nakahata, Yu Kawahara, Jun Horiyama, Takashi Kasahara, Shoji Nara Inst Sci & Technol Grad Sch Informat Sci Ikoma 6300192 Japan Saitama Univ Grad Sch Sci & Engn Saitama 3388570 Japan

This paper studies a variant of the graph partitioning problem, called the evacuation planning problem, which asks us to partition a target area, represented by a graph, into several regions so that each region contains exactly one shelter. Each region must be convex to reduce intersections of evacuation routes, the distance between each point to a shelter must be bounded so that inhabitants can quickly evacuate from a disaster, and the number of inhabitants assigned to each shelter must not exceed the capacity of the shelter. This paper formulates the convexity of connected components as a spanning shortest path forest for general graphs, and proposes a novel algorithm to tackle this multi-objective optimization problem. The algorithm not only obtains a single partition but also enumerates all partitions simultaneously satisfying the above complex constraints, which is difficult to be treated by existing algorithms, using zero-suppressed binary decision diagrams (ZDDs) as a compressed expression. The efficiency of the proposed algorithm is confirmed by the experiments using real-world map data. The results of the experiments show that the proposed algorithm can obtain hundreds of millions of partitions satisfying all the constraints for input graphs with a hundred of edges in a few minutes.

关键词： graph algorithm graph partitioning decision diagram frontier-based search enumeration problem

来源：评论

学校读者我要写书评

暂无评论

Exact algorithms for weak Roman domination

引用

DISCRETE APPLIED MATHEMATICS 2018年 248卷 79-92页

作者： Chapelle, Mathieu Cochefert, Manfred Couturier, Jean-Francois Kratsch, Dieter Letourneur, Romain Liedloff, Mathieu Perez, Anthony IFTS CReSTIC Pole Haute Technol F-08000 Charleville Mezieres France Univ Lorraine Lab Informat Theor & Appl F-57045 Metz 01 France Univ Orleans INSA Ctr Val Loire LIFO EA 4022 FR-45067 Orleans France

We consider the WEAK ROMAN DOMINATION problem. Given an undirected graph G = (V, E), the aim is to find a weak Roman domination function (wrd-function for short) of minimum cost, i.e. a function f : V -> {0, 1, 2} such that every vertex v is an element of V is defended (i.e. there exists a neighbor u of v, possibly u = v, such that f (u) >= 1) and for every vertex v is an element of V with f (v) = 0 there exists a neighbor u of v such that f (u) >= 1 and the function f(u -> v) defined by f(u -> v)(v) = 1, f(u -> v)(u) = f (u) - 1 and f(u -> v)(x) = f(x) otherwise does not contain any undefended vertex. The cost of a wrd-function f is defined by cost(f) = Sigma(v is an element of V)f(v). The trivial enumeration algorithm runs in time O*(3(n)) and polynomial space and is the best one known for the problem so far. We are breaking the trivial enumeration barrier by providing two faster algorithms: we first prove that the problem can be solved in O*(2(n)) time needing exponential space, and then describe an O*(2.2279(n)) algorithm using polynomial space. Our results rely on structural properties of a wrd-function, as well as on the best polynomial space algorithm for the RED-BLUE DOMINATING SET problem. Moreover we show that the problem can be solved in linear-time on interval graphs. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Exact algorithm graph algorithm Roman domination Interval graphs

来源：评论

学校读者我要写书评

暂无评论

New Bounds for Combinatorial Problems and Quasi-Gray Codes

New Bounds for Combinatorial Problems and Quasi-Gray Codes

引用

作者： Das, Debarati Charles University of Prague

This thesis consists of two parts. In part I, a group of combinatorial problems pertaining to strings, boolean matrices and graphs is studied. For given two strings x and y, their edit distance is the minimum number of character insertions, deletions and substitutions required to convert x into y. In this thesis we provide an algorithm that computes a constant approximation of edit distance in truly sub-quadratic time. Based on the provided ideas, we construct a separate sub- quadratic time algorithm that can find an occurrence of a pattern P in a given text T while allowing a few edit errors. Afterwards we study the boolean matrix multiplication (BMM) problem where given two boolean matrices, the aim is to find their product over boolean semi-ring. For this problem, we present two combinatorial models and show in these models BMM requires Ω(n3 /2O( √ log n) ) and Ω(n7/3 /2O( √ log n) ) work respectively. Furthermore, we also give a construction of a sparse sub-graph that preserves the distance between a designated source and any other vertex as long as the total weight increment of all the edges is bounded by some constant. In part II, we study the efficient construction of quasi-Gray codes. We give a construction of space optimal quasi-Gray codes over odd sized alphabets with read complexity 4...

关键词： Boolean matrix multiplication Combinatorial lower bounds Edit distance Pattern matching graph algorithm Quasi-Gray code

来源：评论

学校读者我要写书评

暂无评论

An evaluation of reordering algorithms to reduce the computational cost of the incomplete Cholesky-conjugate gradient method

引用

COMPUTATIONAL & APPLIED MATHEMATICS 2018年第3期37卷 2965-3004页

作者： Gonzaga de Oliveira, Sanderson L. Bernardes, J. A. B. Chagas, G. O. Univ Fed Lavras Lavras Brazil

This paper is concerned with applying bandwidth and profile reduction reordering algorithms prior to computing an incomplete Cholesky factorization and using this as a preconditioner for the conjugate gradient method. Hundreds of reordering algorithms have been proposed to solve the problems of bandwidth and profile reductions since the mid-1960s. In previous publications, a large range of heuristics for bandwidth and/or profile reductions was reviewed. Based on this experience, 13 heuristics were selected as the most promising methods. These are evaluated in this paper along with a variant of the breadth-first search procedure that is proposed. Numerical results confirm the effectiveness of this modified reordering algorithm for linear systems derived from specific application areas. Moreover, the most promising heuristics for several application areas are identified when reducing the computational cost of the incomplete Cholesky-conjugate gradient method.

关键词： Bandwidth reduction Profile reduction Combinatorial optimization Heuristics Metaheuristics Reordering algorithms Sparse matrices Renumbering Ordering graph labeling Conjugate gradient method graph algorithm Sparse symmetric positive-definite linear systems Incomplete Cholesky factorization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：