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

algorithmic aspects of b-disjunctive domination in graphs

JOURNAL OF COMBINATORIAL OPTIMIZATION 2018年第2期36卷 572-590页

作者： Panda, B. S. Pandey, Arti Paul, S. Indian Inst Technol Delhi Dept Math Hauz Khas New Delhi 110016 India Indian Inst Technol Ropar Dept Math Rupnagar 140001 Punjab India Indian Inst Informat Technol Guwahati Dept Comp Sci & Engn GN Bordoloi Rd Gauhati 781001 India

For a fixed integer , a set is called a b-disjunctive dominating set of the graph if for every vertex , v is either adjacent to a vertex of D or has at least b vertices in D at distance 2 from it. The Minimum b-Disjunctive Domination Problem (MbDDP) is to find a b-disjunctive dominating set of minimum cardinality. The cardinality of a minimum b-disjunctive dominating set of G is called the b-disjunctive domination number of G, and is denoted by . Given a positive integer k and a graph G, the b-Disjunctive Domination Decision Problem (bDDDP) is to decide whether G has a b-disjunctive dominating set of cardinality at most k. In this paper, we first show that for a proper interval graph G, is equal to , the domination number of G for and observe that need not be equal to for . We then propose a polynomial time algorithm to compute a minimum cardinality b-disjunctive dominating set of a proper interval graph for . Next we tighten the NP-completeness of bDDDP by showing that it remains NP-complete even in chordal graphs. We also propose a -approximation algorithm for MbDDP, where is the maximum degree of input graph and prove that MbDDP cannot be approximated within for any unless NP DTIME. Finally, we show that MbDDP is APX-complete for bipartite graphs with maximum degree .

关键词： Domination Chordal graph graph algorithm Approximation algorithm NP-complete APX-complete

来源：评论

学校读者我要写书评

暂无评论

Exact values for three domination-like problems in circular and infinite grid graphs of small height

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2019年第3期21卷

作者： Bouznif, M. Darlay, J. Moncel, J. Preissmann, M. A SIS St Etienne France Innovation24 Paris France Univ Toulouse CNRS LAAS Toulouse France Federat Rech Maths Modeler St Martin Dheres France CNRS G SCOP Grenoble France

In this paper we study three domination-like problems, namely identifying codes, locating-dominating codes, and locating-total-dominating codes. We are interested in finding the minimum cardinality of such codes in circular and infinite grid graphs of given height. We provide an alternate proof for already known results, as well as new results. These were obtained by a computer search based on a generic framework, that we developed earlier, for the search of a minimum labeling satisfying a pseudo-d-local property in rotagraphs.

关键词： graph algorithm identifying code locating-dominating code locating-total-dominating code grid

来源：评论

学校读者我要写书评

暂无评论

Entropy promotes charge separation in bulk heterojunction organic photovoltaics

引用

JOURNAL OF PHOTOCHEMISTRY AND PHOTOBIOLOGY A-CHEMISTRY 2019年 382卷

作者： Kawashima, Eisuke Fujii, Mikiya Yamashita, Koichi Univ Tokyo Grad Sch Engn Dept Chem Syst Engn Bunkyo Ku 7-3-1 Hongo Tokyo Japan

Charge separation is one of the crucial processes in the photoelectric conversion of organic photovoltaics. It is considered that organic photovoltaics have low performances because of strong Coulomb attraction. In this work, an entropy-driven charge-separation mechanism was elucidated using a graph algorithm and dynamic Monte Carlo simulations. Helmholtz energies were decreased by entropies, and had a barrier (240-270 meV) at an electron-hole distance of 6 nm;separation efficiencies at interfaces of large donor: small acceptor domains were lower than those at large donor: large acceptor domains, which can be attributed to their higher barrier-separation was promoted by a decreased barrier.

关键词： Organic photovoltaics Morphology Entropy graph algorithm Dynamic Monte Carlo

来源：评论

学校读者我要写书评

暂无评论

The complexity of the Clar number problem and an exact algorithm

引用

JOURNAL OF MATHEMATICAL CHEMISTRY 2018年第2期56卷 597-605页

作者： Berczi-Kovacs, Erika R. Bernath, Attila Eotvos Lorand Univ Dept Operat Res Pazmany Peter Setany 1-C H-1117 Budapest Hungary Eotvos Lorand Univ MTA ELTE Egervary Res Grp Dept Operat Res Pazmany Peter Setany 1-C H-1117 Budapest Hungary

The Clar number of a (hydro)carbon molecule, introduced by Clar (The aromatic sextet, 1972), is the maximum number of mutually disjoint resonant hexagons in the molecule. Calculating the Clar number can be formulated as an optimization problem on 2-connected plane graphs. Namely, it is the maximum number of mutually disjoint even faces a perfect matching can simultaneously alternate on. It was proved by Abeledo and Atkinson (Linear Algebra Appl 420(2):441-448, 2007) that the Clar number can be computed in polynomial time if the plane graph has even faces only. We prove that calculating the Clar number in general 2-connected plane graphs is -hard. We also prove -hardness of the maximum independent set problem for 2-connected plane graphs with odd faces only, which may be of independent interest. Finally, we give an exact algorithm that determines the Clar number of a given 2-connected plane graph. The algorithm has a polynomial running time if the length of the shortest odd join in the planar dual graph is fixed, which gives an efficient algorithm for some fullerene classes, such as carbon nanotubes.

关键词： Clar number Fullerene Carbon nanotubes Complexity Planar graph graph algorithm

来源：评论

学校读者我要写书评

暂无评论

A safe and complete algorithm for metagenomic assembly

引用

algorithmS FOR MOLECULAR BIOLOGY 2018年第1期13卷 1-12页

作者： Acosta, Nidia Obscura Makinen, Veli Tomescu, Alexandru I. Univ Helsinki Helsinki Inst Informat Technol Dept Comp Sci Helsinki Finland

Background: Reconstructing the genome of a species from short fragments is one of the oldest bioinformatics problems. Metagenomic assembly is a variant of the problem asking to reconstruct the circular genomes of all bacterial species present in a sequencing sample. This problem can be naturally formulated as finding a collection of circular walks of a directed graph G that together cover all nodes, or edges, of G. Approach: We address this problem with the "safe and complete" framework of Tomescu and Medvedev (Research in computational Molecular biology-20th annual conference, RECOMB 9649: 152-163, 2016). An algorithm is called safe if it returns only those walks (also called safe) that appear as subwalk in all metagenomic assembly solutions for G. A safe algorithm is called complete if it returns all safe walks of G. Results: We give graph-theoretic characterizations of the safe walks of G, and a safe and complete algorithm finding all safe walks of G. In the node-covering case, our algorithm runs in time O(m(2) + n(3)), and in the edge-covering case it runs in time O(m(2)n);n and m denote the number of nodes and edges, respectively, of G. This algorithm constitutes the first theoretical tight upper bound on what can be safely assembled from metagenomic reads using this problem formulation.

关键词： Genome assembly Contig assembly Metagenomics graph algorithm Circular walk

来源：评论

学校读者我要写书评

暂无评论

Automatic Multi-Document Summarization Based on Keyword Density and Sentence-Word graphs

引用

Journal of Shanghai Jiaotong university(Science) 2018年第4期23卷 584-592页

作者： YE Feiyue XU Xinchen School of Computer Engineering and Science Shanghai UniversityShanghai 200444China

As a fundamental and effective tool for document understanding and organization, multi-document summarization enables better information services by creating concise and informative reports for large collections of documents. In this paper, we propose a sentence-word two layer graph algorithm combining with keyword density to generate the multi-document summarization, known as graph ＆ Keywordp. The traditional graph methods of multi-document summarization only consider the influence of sentence and word in all documents rather than individual documents. Therefore, we construct multiple word graph and extract right keywords in each document to modify the sentence graph and to improve the significance and richness of the summary. Meanwhile, because of the differences in the words importance in documents, we propose to use keyword density for the summaries to provide rich content while using a small number of words. The experiment results show that the graph ＆ Keywordp method outperforms the state of the art systems when tested on the Duc2004 data set. Key words： multi-document, graph algorithm, keyword density, graph ＆ Keywordp, Due2004

关键词： multi-document graph algorithm keyword density graph & Keywordρ Duc2004

来源：评论

学校读者我要写书评

暂无评论

Traversal with Enumeration of Geometric graphs in Bounded Space

引用

JOURNAL OF INTERCONNECTION NETWORKS 2019年第4期19卷

作者： Khakabimamaghani, Sahand Masjoody, Masood Stacho, Ladislav Simon Fraser Univ Dept Comp Sci 8888 Univ Dr Burnaby BC V5A 1S6 Canada Simon Fraser Univ Dept Math 8888 Univ Dr Burnaby BC V5A 1S6 Canada

In this paper, we provide an algorithm for traversing geometric graphs which visits all vertices and reports every vertex and edge exactly once. To achieve this, we combine a given geometric graph G with the integer lattice, seen as a graph, in such a way that the resulting hypothetical graph can be traversed using a known algorithm which is based on face routing. To overcome the problem with hypothetical vertices and edges, we develop an algorithm for visiting any k-th neighborhood of a vertex in a graph straight-line drawn in the plane using O(k log k) memory. The memory needed to complete the traversal of a geometric graph then turns out to depend on the maximum graph distance among pairs of distinct vertices of G whose Euclidean distance is greater than one and less than 2 root 2.

关键词： graph algorithm traversal geometric graph quasi-planar subdivision

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Designing and implementing a heuristic cross-architecture combination for graph traversal

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2017年 108卷 95-105页

作者： You, Yang Fu, Haohuan Bader, David Yang, Guangwen Tsinghua Univ Minist Educ Key Lab Earth Syst Modeling Beijing Peoples R China Tsinghua Univ Ctr Earth Syst Sci Beijing Peoples R China Tsinghua Univ Dept Comp Sci & Technol Beijing Peoples R China Univ Calif Berkeley Div Comp Sci Berkeley CA 94720 USA Georgia Inst Technol Coll Comp Atlanta GA 30332 USA

Breadth-First Search (BFS) is widely used in real-world applications including computational biology, social networks, and electronic design automation. The most effective BFS approach has been shown to be a combination of top-down and bottom-up approaches. Such hybrid techniques need to identify a switching point which is conventionally found through expensive trial-and-error and exhaustive search routines. We present an adaptive method based on regression analysis that enables dynamic switching at runtime with little overhead. We improve the performance of our method by exploiting popular heterogeneous platforms and efficiently design the approach for a given architecture. A 155 x speedup is achieved over the standard top-down approach on GPUs. Our approach is the first to combine top-down and bottom-up across different architectures. Unlike combination on a single architecture, a mistuned switching point may significantly decrease the performance of cross-architecture combination. Our adaptive method can predict the switching point with high accuracy, leading to 7 x speedup compared to the switching point in average case (1000 switching points). (C) 2016 Elsevier Inc. All rights reserved.

关键词： graph algorithm Data-intensive Cross-architecture optimization Knights corner MIC Kepler K20x GPU Combination Regression analysis

来源：评论

学校读者我要写书评

暂无评论

Characterizing Star-PCGs 24th

Characterizing Star-PCGs

引用

24th International Computing and Combinatorics Conference (COCOON)

作者： Xiao, Mingyu Nagamochi, Hiroshi Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Sichuan Peoples R China Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto Japan

ISBN: (纸本)9783319947761;9783319947754

A graph G is called a pairwise compatibility graph (PCG, for short) if it admits a tuple (T, w, d(min), d(max)) of a tree T whose leaf set is equal to the vertex set of G, a non-negative edge weight w, and two non-negative reals d(min) <= d(max) such that G has an edge between two vertices u, v is an element of V if and only if the distance between the two leaves u and v in the weighted tree (T, w) is in the interval [d(min), d(max)]. The tree T is also called a witness tree of the PCG G. The problem of testing if a given graph is a PCG is not known to be NP -hard yet. To obtain a complete characterization of PCGs is a wide open problem in computational biology and graph theory. In the literature, most witness trees admitted by known PCGs are stars and caterpillars. In this paper, we give a complete characterization for a graph to be a star-PCG (a PCG that admits a star as its witness tree), which provides us the first polynomial-time algorithm for recognizing star-PCGs.

关键词： Pairwise compatibility graph Polynomial-time algorithm graph algorithm graph theory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：