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

Approximation to the minimum cost edge installation problem

18th International Symposium on algorithms and Computations (ISAAC 2007)

作者： Morsy, Ehab Nagamochi, Hiroshi Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto Japan

ISBN: (纸本)9783540771180

We consider the minimum cost edge installation problem (MCEI) in a graph G = (V, E) with edge weight w (e) >= 0, e is an element of E. We are given a vertex s is an element of V designated as a sink, an edge capacity lambda > 0, and a source set S subset of V with demand q(v) is an element of [0, lambda], v is an element of S. For any edge e is an element of E, we are allowed to install an integer number h(e) of copies of e. The MCEI asks to send demand q(v) from each source v is an element of S along a single path P-v to the sink s. A set of such paths can pass through a single copy of an edge in G as long as the total demand along the paths does not exceed the edge capacity lambda. The objective is to find a set P = {P-v vertical bar v is an element of S} of paths of G that minimizes the installing cost Sigma(e is an element of E) h(e)w(e). In this paper, we propose a (15/8 + rho(ST))-approximation algorithm to the MCEI, where PST is any approximation ratio achievable for the Steiner tree problem.

关键词： approximation algorithm graph algorithm routing problem network optimization

来源：评论

学校读者我要写书评

暂无评论

An Analysis of Reordering algorithms to Reduce the Computational Cost of the Jacobi-Preconditioned CG Solver Using High-Precision Arithmetic 17th

An Analysis of Reordering Algorithms to Reduce the Computati...

引用

17th International Conference on Computational Science and its Applications (ICCSA)

作者： Gonzaga de Oliveira, Sanderson L. Chagas, Guilherme Oliveira Barreto Bernardes, Junior Assis Univ Fed Lavras Lavras MG Brazil Inst Nacl Pesquisas Espaciais Sao Paulo Brazil

ISBN: (纸本)9783319623924;9783319623917

Several heuristics for bandwidth and profile reductions have been proposed since the 1960s. In systematic reviews, 133 heuristics applied to these problems have been found. The results of these heuristics have been analyzed so that, among them, 13 were selected in a manner that no simulation or comparison showed that these algorithms could be outperformed by any other algorithm in the publications analyzed, in terms of bandwidth or profile reductions and also considering the computational costs of the heuristics. Therefore, these 13 heuristics were selected as the most promising low-cost methods to solve these problems. Based on this experience, this article reports that in certain cases no heuristic for bandwidth or profile reduction can reduce the computational cost of the Jacobi-preconditioned Conjugate Gradient Method when using high-precision numerical computations.

关键词： Bandwidth reduction Profile reduction Conjugate Gradient Method graph labeling Reordering algorithms Sparse matrices graph algorithm High-precision arithmetic Ordering Sparse symmetric positive-definite linear systems Combinatorial optimization Heuristics

来源：评论

学校读者我要写书评

暂无评论

Shared-Memory Parallel Maximal Biclique Enumeration 26

Shared-Memory Parallel Maximal Biclique Enumeration

引用

26th International Conference on High Performance Computing, Data and Analytics (HiPCW)

作者： Das, Apurba Tirthapura, Srikanta Natl Univ Singapore Singapore Singapore Iowa State Univ Ames IA USA

ISBN: (纸本)9781728145358

We present shared memory parallel algorithms for maximal biclique enumeration (MBE), the task of enumerating all complete dense subgraphs (maximal bicliques) from a bipartite graph, which is widely used in the analysis of social, biological, and transactional networks. Since MBE is computationally expensive, it is necessary to use parallel computing to scale to large graphs. Our parallel algorithm ParMBE efficiently uses the power of multiple cores that share memory. From a theoretical view, ParMBE is work-efficient with respect to a state-of-the-art sequential algorithm. Our experimental evaluation shows that ParMBE scales well up to 64 cores, and is significantly faster than current parallel algorithms. Since ParMBE was yielding a super-linear speedup compared to the sequential algorithm on which it was based (Mine LMBC), we develop an improved sequential algorithm FMBE, through "sequentializing" ParMBE.

关键词： dynamic graph graph algorithm maximal biclique enumeration shared memory parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

A Node-Embedding Features Based Machine Learning Technique for Dynamic Malware Detection 5

A Node-Embedding Features Based Machine Learning Technique f...

引用

5th IEEE Conference on Dependable and Secure Computing (IEEE DSC)

作者： Rai, Sudhir Kumar Mittal, Ashish Mittal, Sparsh Indian Inst Technol IIT Roorkee Roorkee Uttar Pradesh India

ISBN: (数字)9781665421416

ISBN: (纸本)9781665421416

As the malware menace exacerbates, dynamic malware detection (DMD) has become even more critical. In this paper, we present a machine-learning-based DMD technique. We propose generating node embedding features (NEFs) from process execution chains. We use NEFs and other features based on the command line, file path, and action taken by a process and feed them to our machine learning (ML) classification algorithms. We evaluated two ML classifiers, viz., light gradient boosting machine (LGBM) and XGBoost. We perform experiments on a real-world dataset provided by a leading anti-virus company. Our technique achieves high accuracy, and the use of NEFs improves the predictive performance of ML classification algorithms. Also, NEFs are found to be highly important in both these algorithms.

关键词： Dynamic malware detection Node2Vec graph algorithm machine learning classification

来源：评论

学校读者我要写书评

暂无评论

Reconfiguring Directed Trees in a Digraph 27th

Reconfiguring Directed Trees in a Digraph

引用

27th International Computing and Combinatorics Conference (COCOON)

作者： Ito, Takehiro Iwamasa, Yuni Kobayashi, Yasuaki Nakahata, Yu Otachi, Yota Wasa, Kunihiro Tohoku Univ Grad Sch Informat Sci Sendai Miyagi Japan Kyoto Univ Grad Sch Informat Kyoto Japan Nagoya Univ Grad Sch Informat Nagoya Aichi Japan Toyohashi Univ Technol Dept Comp Sci & Engn Toyohashi Aichi Japan

ISBN: (纸本)9783030895433;9783030895426

In this paper, we investigate the computational complexity of subgraph reconfiguration problems in directed graphs. More specifically, we focus on the problem of reconfiguring directed trees in a digraph, where a directed tree is a directed graph such that its underlying undirected graph forms a tree and every vertex except for exactly one vertex has in-degree 1. Given two directed trees in a digraph, the goal of the problem is to determine whether there is a (reconfiguration) sequence of directed trees between two given ones such that each tree in the sequence can be obtained from the previous one by removing an arc and then adding another arc. We show that this problem can be solved in polynomial time, whereas the problem is PSPACE-complete when we restrict directed trees in a reconfiguration sequence to form directed paths. We also show that there is a polynomial-time algorithm for finding a shortest reconfiguration sequence between two spanning directed trees.

关键词： Combinatorial reconfiguration graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximating the k-Splittable Capacitated Network Design Problem

Approximating the k-Splittable Capacitated Network Design Pr...

引用

39th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)

作者： Morsy, Ehab Nanyang Technol Univ Div Math Sci Singapore 637371 Singapore Suez Canal Univ Dept Math Ismailia 22541 Egypt

ISBN: (纸本)9783642358432

We consider the k-splittable capacitated network design problem (kSCND) in a graph G = (V, E) with edge weight w(e) >= 0, e is an element of E. We are given a vertex s is an element of V designated as a sink, a cable capacity lambda > 0, and a source set S subset of V with demand q(v) >= 0, v is an element of S. For any edge e is an element of E, we are allowed to install an integer number h(e) of copies of e. The kSCND asks to simultaneously send demand q(v) from each source v is an element of S along at most k paths to the sink s. A set of such paths can pass through a single copy of an edge in G as long as the total demand along the paths does not exceed the cable capacity lambda. The objective is to find a set P of paths of G that minimizes the installing cost Sigma(e is an element of Eh)(e)w(e). In this paper, we propose a ((k + 1)/ k + rho(ST))-approximation algorithm to the kSCND, where rho(ST) is any approximation ratio achievable for the Steiner tree problem.

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

来源：评论

学校读者我要写书评

暂无评论

EBOARST: An Efficient Edge-Based Obstacle-Avoiding Rectilinear Steiner Tree Construction algorithm

EBOARST: An Efficient Edge-Based Obstacle-Avoiding Rectiline...

引用

International Symposium on Physical Design (ISPD)

作者： Long, Jieyi Zhou, Hai Memik, Seda Ogrenci Northwestern Univ Dept Elect Engn & Comp Engn Evanston IL 60208 USA

Obstacle-avoiding Steiner routing has arisen as a fundamental problem in the physical design of modern VLSI chips. In this paper, we present EBOARST, an efficient four-step algorithm to construct a rectilinear obstacle-avoiding Steiner tree for a given set of pins and a given set of rectilinear obstacles. Our contributions are fourfold. First, we propose a novel algorithm, which generates sparse obstacle-avoiding spanning graphs efficiently. Second, we present a fast algorithm for the minimum terminal spanning tree construction step, which dominates the running time of several existing approaches. Third, we present an edge-based heuristic, which enables us to perform both local and global refinements, leading to Steiner trees with small lengths. Finally, we discuss a refinement technique called segment translation to further enhance the quality of the trees. The time complexity of our algorithm is O(n log n). Experimental results on various benchmarks show that our algorithm achieves 16.56 times speedup on average, while the average length of the resulting obstacle-avoiding rectilinear Steiner trees is only 0.46% larger than the best existing solution.

关键词： graph algorithm obstacle-avoiding routing Steiner tree

来源：评论

学校读者我要写书评

暂无评论

Implicit Enumeration of Topological-Minor-Embeddings and Its Application to Planar Subgraph Enumeration 14th

Implicit Enumeration of Topological-Minor-Embeddings and Its...

引用

14th International Conference and Workshops on algorithms and Computation (WALCOM)

作者： Nakahata, Yu Kawahara, Jun Horiyama, Takashi Minato, Shin-ichi Kyoto Univ Kyoto Japan Hokkaido Univ Sapporo Hokkaido Japan

ISBN: (纸本)9783030398811;9783030398804

Given graphs G and H, we propose a method to implicitly enumerate topological-minor-embeddings of H in G using decision diagrams. We show a useful application of our method to enumerating subgraphs characterized by forbidden topological minors, that is, planar, outerplanar, series-parallel, and cactus subgraphs. Computational experiments show that our method can find all planar subgraphs in a given graph at most five orders of magnitude faster than a naive backtracking-based method.

关键词： graph algorithm Enumeration problem Decision diagram Frontier-based search Topological minor

来源：评论

学校读者我要写书评

暂无评论

Fast and Scalable NUMA-based Thread Parallel Breadth-first Search 13

Fast and Scalable NUMA-based Thread Parallel Breadth-first S...

引用

International Conference on High Performance Computing and Simulation (HPCS)

作者： Yasui, Yuichiro Fujisawa, Katsuki Kyushu Univ Nishi Ku 744 Motooka Fukuoka 812 Japan JST COI Nishi Ku Fukuoka Japan JST CREST Nishi Ku Fukuoka Japan

ISBN: (纸本)9781467378130

The breadth-first search (BFS) is one of the most centric kernels in graph processing. Beamer's direction-optimizing BFS algorithm, which selects one of two traversal directions at each level, can reduce unnecessary edge traversals. In a previous paper, we presented an efficient BFS for a non-uniform memory access (NUMA)-based system, in which the NUMA architecture was carefully considered. In this paper, we investigate the locality of memory accesses in terms of the communication with remote memories in a BFS for a NUMA system, and describe a fast and highly scalable implementation. Our new implementation achieves performance rates of 174.704 billion edges per second for a Kronecker graph with 2(33) vertices and 2(37) edges on two racks of a SGI UV 2000 system with 1,280 threads. The implementations described in this paper achieved the fastest entries for a shared-memory system in the June 2014 and November 2014 graph500 lists, and produced the most energy-efficient entries in the second, third, and fourth Green graph500 lists (big data category).

关键词： Breadth-first search graph algorithm parallel algorithm NUMA-aware graph500 benchmark

来源：评论

学校读者我要写书评

暂无评论

CONNECTED LIAR'S DOMINATION IN graphS: COMPLEXITY AND algorithmS

引用

DISCRETE MATHEMATICS algorithmS AND APPLICATIONS 2013年第4期5卷 1350024-1-1350024-16页

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

A subset L subset of V of a graph G = (V, E) is called a connected liar's dominating set of G if (i) for all v. V, |NG[v] n L| >= 2, ( ii) for every pair u, v is an element of V of distinct vertices, |(N-G[u]. N-G[v]) boolean AND L| >= 3, and ( iii) the induced subgraph of G on L is connected. In this paper, we initiate the algorithmic study of minimum connected liar's domination problem by showing that the corresponding decision version of the problem is NP-complete for general graph. Next we study this problem in subclasses of chordal graphs where we strengthen the NP-completeness of this problem for undirected path graph and prove that this problem is linearly solvable for block graphs. Finally, we propose an approximation algorithm for minimum connected liar's domination problem and investigate its hardness of approximation in general graphs.

关键词： Domination liar's domination chordal graph graph algorithm NP-completeness approximation algorithm APX-completeness

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：