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

algorithmICA 2020年第10期82卷 3066-3090页

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

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. 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. How to recognize PCGs is a wide-open problem in the literature. This paper gives 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

来源：评论

学校读者我要写书评

暂无评论

Complexity and algorithms for Semipaired Domination in graphs

引用

THEORY OF COMPUTING SYSTEMS 2020年第7期64卷 1225-1241页

作者： Henning, Michael A. Pandey, Arti Tripathi, Vikash Univ Johannesburg Dept Math & Appl Math ZA-2006 Auckland Pk South Africa Indian Inst Technol Ropar Dept Math Nangal Rd Rupnagar 140001 Punjab India

For a graph G = (V, E) with no isolated vertices, a set D subset of V is called a semipaired dominating set of G if (i) D is a dominating set of G, and (ii) D can be partitioned into two element subsets such that the vertices in each two element set are at distance at most two. The minimum cardinality of a semipaired dominating set of G is called the semipaired domination number of G, and is denoted by gamma(pr2)(G). TheMINIMUM SEMIPAIRED DOMINATION problem is to find a semipaired dominating set of G of cardinality gamma(pr2)(G). In this paper, we initiate the algorithmic study of the MINIMUM SEMIPAIRED DOMINATION problem. We show that the decision version of the MINIMUM SEMIPAIRED DOMINATION problem is NP-complete for bipartite graphs and chordal graphs. On the positive side, we present a linear-time algorithm to compute a minimum cardinality semipaired dominating set of interval graphs. We also propose a 1 + ln(2 Delta + 2)-approximation algorithm for the MINIMUM SEMIPAIRED DOMINATION problem, where Delta denotes the maximum degree of the graph and show that the MINIMUM SEMIPAIRED DOMINATION problem cannot be approximated within (1 - epsilon) ln vertical bar V vertical bar for any epsilon > 0 unless P=NP.

关键词： Domination Semipaired domination Interval graphs graph algorithm NP-complete Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Maximum weight induced matching in some subclasses of bipartite graphs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2020年第3期40卷 713-732页

作者： Panda, B. S. Pandey, Arti Chaudhary, Juhi Dane, Piyush Kashyap, Manav Indian Inst Technol Delhi Dept Math New Delhi 110016 India Indian Inst Technol Ropar Dept Math Nangal Rd Rupnagar 140001 Punjab India

A subset M subset of E of edges of a graph G=(V,E) is called amatchinginGif no two edges inMshare a common vertex. A matchingMinGis called aninduced matchingifG[M], the subgraph ofGinduced byM, is the same asG[S], the subgraph ofGinduced byS={v is an element of V|vertical bar v}vis incident on an edge ofM}. TheMaximum Induced Matchingproblem is to find an induced matching of maximum cardinality. Given a graphGand a positive integerk, theInduced Matching Decisionproblem is to decide whetherGhas an induced matching of cardinality at leastk. TheMaximum Weight Induced Matchingproblem in a weighted graph G = (V,E) in which the weight of each edge is a positive real number, is to find an induced matching such that the sum of the weights of its edges is maximum. It is known that theInduced Matching Decisionproblem and hence theMaximum Weight Induced Matchingproblem is known to be NP-complete for general graphs and bipartite graphs. In this paper, we strengthened this result by showing that theInduced Matching Decisionproblem is NP-complete for star-convex bipartite graphs, comb-convex bipartite graphs, and perfect elimination bipartite graphs, the subclasses of the class of bipartite graphs. On the positive side, we propose polynomial time algorithms for theMaximum Weight Induced Matchingproblem for circular-convex bipartite graphs and triad-convex bipartite graphs by making polynomial time reductions from theMaximum Weight Induced Matchingproblem in these graph classes to theMaximum Weight Induced Matchingproblem in convex bipartite graphs.

关键词： Matching Induced matching Bipartite graphs graph algorithm NP-complete

来源：评论

学校读者我要写书评

暂无评论

CrawlSN: community-aware data acquisition with maximum willingness in online social networks

引用

DATA MINING AND KNOWLEDGE DISCOVERY 2020年第5期34卷 1589-1620页

作者： Hsu, Bay-Yuan Tu, Chia-Lin Chang, Ming-Yi Shen, Chih-Ya Natl Taipei Univ Dept Comp Sci New Taipei Taiwan Natl Tsing Hua Univ Dept Comp Sci Hsinchu Taiwan

Real social network datasets with community structures are critical for evaluating various algorithms in Online Social Networks (OSNs). However, obtaining such community data from OSNs has recently become increasingly challenging due to privacy issues and government regulations. In this paper, we thus make our first attempt to address two important factors, i.e., user willingness and existence of community structure, to obtain more complete OSN data. We formulate a new research problem, namelyCommunity-aware Data Acquisition with Maximum Willingness in Online Social Networks(CrawlSN), to identify a group of users from an OSN, such that the group is a socially tight community and the users' willingness to contribute data is maximized. We prove that CrawlSN is NP-hard and inapproximable within any factor unless, and propose an effective algorithm, namedCommunity-aware Group Identification with Maximum Willingness(CIW) with various processing strategies. We conduct an evaluation study with 1093 volunteers to validate our problem formulation and demonstrate that CrawlSN outperforms the other alternatives. We also perform extensive experiments on 7 real datasets and show that the proposed CIW outperforms the other baselines in both solution quality and efficiency.

关键词： Social networks graph algorithm Data acquisition

来源：评论

学校读者我要写书评

暂无评论

Evolving reordering algorithms using an ant colony hyperheuristic approach for accelerating the convergence of the ICCG method

引用

ENGINEERING WITH COMPUTERS 2020年第4期36卷 1857-1873页

作者： de Oliveira, S. L. Gonzaga Silva, L. M. Univ Fed Lavras Dept Ciencia Computacao Lavras Brazil

This paper proposes a novel ant colony hyperheuristic approach for reordering the rows and columns of symmetric positive definite matrices. This ant colony hyperheuristic approach evolves heuristics for bandwidth reduction applied to instances arising from specific application areas with the objective of generating low-cost reordering algorithms. This paper evaluates the resulting reordering algorithm in each application area against state-of-the-art reordering algorithms with the purpose of reducing the running times of the zero-fill incomplete Cholesky-preconditioned conjugate gradient method. The results obtained on a wide-ranging set of standard benchmark matrices show that the proposed approach compares favorably with state-of-the-art reordering algorithms when applied to instances arising from computational fluid dynamics, structural, and thermal problems.

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

来源：评论

学校读者我要写书评

暂无评论

On the Konig deficiency of zero-reducible graphs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2020年第1期39卷 273-292页

作者： Bartha, Miklos Kresz, Miklos Mem Univ Newfoundland Dept Comp Sci St John NF A1B 3X5 Canada Univ Szeged Juhasz Gyula Fac Educ Boldogasszony Sgt 6 H-6725 Szeged Hungary InnoRenew CoE Izola 6310 Slovenia Univ Primorska Koper 6000 Slovenia

A confluent and terminating reduction system is introduced for graphs, which preserves the number of their perfect matchings. A union-find algorithm is presented to carry out reduction in almost linear time. The Konig property is investigated in the context of reduction by introducing the Konig deficiency of a graph G as the difference between the vertex covering number and the matching number of G. It is shown that the problem of finding the Konig deficiency of a graph is NP-complete even if we know that the graph reduces to the empty graph. Finally, the Konig deficiency of graphs G having a vertex v such that G-v has a unique perfect matching is studied in connection with reduction.

关键词： graph matching Independent set Konig property graph reduction graph algorithm

来源：评论

学校读者我要写书评

暂无评论

An ant colony hyperheuristic approach for matrix bandwidth reduction

引用

APPLIED SOFT COMPUTING 2020年 94卷 106434-106434页

作者： de Oliveira, S. L. Gonzaga Silva, L. M. Univ Fed Lavras Lavras Brazil

This paper considers the bandwidth reduction problem for large-scale matrices in serial computations. A heuristic for bandwidth reduction reorders the rows and columns of a given sparse matrix so that the method places entries with a nonzero value as close to the main diagonal as possible. Bandwidth optimization is a critical issue for many scientific and engineering applications. In this regard, this paper proposes an ant colony hyperheuristic approach for the bandwidth reduction of symmetric and nonsymmetric matrices. The ant colony hyperheuristic approach evolves and selects graph theory bandwidth reduction algorithms for application areas. This paper evaluates the resulting heuristics for bandwidth reduction in each application area against the most promising low-cost heuristics for bandwidth reduction. This paper also includes a numerical examination of the current state-of-the-art metaheuristic algorithms for matrix bandwidth reduction. The results yielded on a wide-ranging set of standard benchmark matrices showed that the proposed approach outperformed state-of-the-art low-cost heuristics for bandwidth reduction when applied to problem cases arising from several application areas, clearly indicating the promise of the proposal. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Bandwidth reduction Sparse matrix Ant colony optimization Hyperheuristic Reordering algorithms Renumbering Ordering graph labeling graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Reconfiguring spanning and induced subgraphs

引用

THEORETICAL COMPUTER SCIENCE 2020年 806卷 553-566页

作者： Hanaka, Tesshu Ito, Takehiro Mizuta, Haruka Moore, Benjamin Nishimura, Naomi Subramanya, Vijay Suzuki, Akira Vaidyanathan, Krishna Chuo Univ Fac Sci & Engn Bunkyo Ku 1-13-27 Kasuga Tokyo 1128551 Japan Tohoku Univ Grad Sch Informat Sci Aoba Ku 6-6-05 Aoba Sendai Miyagi 9808579 Japan Univ Waterloo Dept Combinator & Optimizat 200 Univ Ave West Waterloo ON N2L 3G1 Canada Univ Waterloo David R Cheriton Sch Comp Sci 200 Univ Ave West Waterloo ON N2L 3G1 Canada

SUBgraph RECONFIGURATION is a family of problems focusing on the reachability of the solution space in which feasible solutions are subgraphs, represented either as sets of vertices or sets of edges, satisfying a prescribed graph structure property. Although there has been previous work that can be categorized as SUBgraph RECONFIGURATION, most of the related results appear under the name of the property under consideration;for example, independent set, clique, and matching. In this paper, we systematically clarify the complexity status of SUBgraph RECONFIGURATION with respect to graph structure properties. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Combinatorial reconfiguration graph algorithm

来源：评论

学校读者我要写书评

暂无评论

An Optimal O(nm) algorithm for Enumerating All Walks Common to All Closed Edge-covering Walks of a graph

引用

ACM TRANSACTIONS ON algorithmS 2019年第4期15卷 48-48页

作者： Cairo, Massimo Medvedev, Paul Acosta, Nidia Obscura Rizzi, Romeo Tomescu, Alexandru, I Univ Trento Dept Math Via Sommarive 14 I-38123 Povo Italy Penn State Univ Dept Comp Sci & Engn W316 Westgate Bldg University Pk PA 16802 USA Aalto Univ Aalto SCI Comp Sci Konemiehentie 2 Espoo 02150 Finland Univ Verona Dept Comp Sci CaVignal 2Str Grazie 15 I-37134 Verona Italy Univ Helsinki Dept Comp Sci POB 68 FI-00014 Helsinki Finland

In this article, we consider the following problem. Given a directed graph G, output all walks of G that are sub-walks of all closed edge-covering walks of G. This problem was first considered by Tomescu and Medvedev (RECOMB 2016), who characterized these walks through the notion of omnitig. Omnitigs were shown to be relevant for the genome assembly problem from bioinformatics, where a genome sequence must be assembled from a set of reads from a sequencing experiment. Tomescu and Medvedev (RECOMB 2016) also proposed an algorithm for listing all maximal omnitigs, by launching an exhaustive visit from every edge. In this article, we prove new insights about the structure of omnitigs and solve several open questions about them. We combine these to achieve an O(nm)-time algorithm for outputting all the maximal omnitigs of a graph (with n nodes and m edges). This is also optimal, as we show families of graphs whose total omnitig length is Omega(nm). We implement this algorithm arid show that it is 9-12 times faster in practice than the one of Tomescu and Medvedev (RECOMB 2016).

关键词： Genome assembly safe and complete algorithm graph algorithm edge-covering walk strong bridge

来源：评论

学校读者我要写书评

暂无评论

Finding Small and Large k-Clique Instances on a Quantum Computer

IEEE TRANSACTIONS ON QUANTUM ENGINEERING

引用

IEEE TRANSACTIONS ON QUANTUM ENGINEERING 2020年 1卷 1页

作者： Metwalli, Sara Ayman Le Gall, Francois Van Meter, Rodney Keio Univ Quantum Comp Ctr Tokyo 1088345 Japan Nagoya Univ Grad Sch Math Nagoya Aichi 4648601 Japan

algorithms for triangle finding, the smallest nontrivial instance of the k-clique problem, have been proposed for quantum computers. Still, those algorithms assume the use of fixed access time quantum RAM. In this article, we present a practical gate-based approach to both the triangle-finding problem and its NP-hard k-clique generalization. We examine both constant factors for near-term implementation on a noisy intermediate scale quantum computing (NISQ) device and the scaling of the problem to evaluate long-term use of quantum computers. We compare the time complexity and circuit practicality of the theoretical approach and actual implementation. We propose and apply two different strategies to the k-clique problem, examining the circuit size of Qiskit implementations. We analyze our implementations by simulating triangle finding with various error models, observing the effect on damping the amplitude of the correct answer, and compare to execution on six real IBM quantum machines. Finally, we estimate the approximate quantum volume needed so that the smallest instance of our approach can be executable with minimal error on a real NISQ device.

关键词： Clique finding graph algorithm Grover's algorithm noisy intermediate scale quantum computing (NISQ)

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：