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

Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems

THEORETICAL COMPUTER SCIENCE 2017年第PartA期657卷 86-97页

作者： Xiao, Mingyu Kou, Shaowei Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 611731 Peoples R China

A dissociation set in a graph G = (V, E) is a vertex subset D such that the subgraph G[D] induced on D has vertex degree at most 1. A 3-path vertex cover in a graph is a vertex subset C such that every path of three vertices contains at least one vertex from C. A vertex set D is a dissociation set if and only if V \ D is a 3-path vertex cover. There are many applications for dissociation sets and 3-path vertex covers. However, it is NP-hard to compute a dissociation set of maximum size or a 3-path vertex cover of minimum size in graphs. Several exact algorithms have been proposed for these two problems and they can be solved in O*(1.4658(n)) time in n-vertex graphs. In this paper, we reveal some interesting structural properties of the two problems, which allow us to solve them in O*(1.4656(n)) time and polynomial space or O*(1.3659(n)) time and exponential space. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Exact algorithm graph algorithm Dissociation number 3-path vertex cover Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

algorithmic aspects of open neighborhood location-domination in graphs

引用

DISCRETE APPLIED MATHEMATICS 2017年第Part1期216卷 290-306页

作者： Panda, B. S. Pandey, Arti Indian Inst Technol Delhi Dept Math New Delhi 110016 India

A set D subset of V of a graph G = (V, E) is called an open neighborhood locating-dominating set (OLD-set) if (i)N-G(v) boolean AND D not equal empty set for all v is an element of V, and (ii)N-G(u) boolean AND D not equal N-G(v) boolean AND D for every pair of distinct vertices u, v is an element of V. Given a graph G = (V, E), the MIN OLD-SET problem is to find an OLD-set of minimum cardinality. Given a graph G = (V, E) and a positive integer k, the DECIDE OLD-SET problem is to decide whether G has an OLD-set of cardinality at most k. The DECIDE OLD-SET problem is known to NP-complete for general graphs. In this paper we extend the NP-completeness result of the DECIDE OLD-SET problem by showing that it remains NP-complete for bipartite graphs, planar graphs, split graphs and doubly chordal graphs. We prove that the DECIDE OLD-SET problem can be solved in linear time for bounded tree-width graphs. We, then, propose a linear time algorithm for the MIN OLD SET problem in trees. We also propose a (2 + 3 ln Delta)-approximation algorithm for the MIN OLD-SET problem and show that the MIN OLD-SET problem cannot be approximated within 1/2(1 - epsilon) ln vertical bar V vertical bar for any epsilon > 0 unless NP subset of DTIME(vertical bar V vertical bar(0(log log vertical bar V vertical bar))) Finally, we prove that the MIN OLD-SET problem is APX-complete for bipartite graphs of maximum degree 3. (C) 2015 Elsevier B.V. All rights reserved.

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

来源：评论

学校读者我要写书评

暂无评论

Alliances in graphs of bounded clique-width

引用

DISCRETE APPLIED MATHEMATICS 2017年 223卷 91-97页

作者： Kiyomi, Masashi Otachi, Yota Yokohama City Univ Int Coll Arts & Sci Kanazawa Ku 22-2 Seto Yokohama Kanagawa 2360027 Japan Japan Adv Inst Sci & Technol Sch Informat Sci Asahidai 1-1 Nomi Ishikawa 9231292 Japan

An alliance in a graph is a set of vertices that is either safe under attacks from the neighborhood (defensive), capable of attacking its neighbors (offensive), or simultaneously defensive and offensive (powerful). An alliance is global if all nonmembers are adjacent to some members of the alliance. The concept of alliances was introduced by Kristiansen et al. (2004). After that many results concerning the complexity for finding a minimum alliance were shown. It was shown that the problem of finding a minimum alliance of any variant is NP-hard in general. For some variants, it was shown that the problem becomes polynomial time solvable when restricted to trees or series-parallel graphs. In this paper, we show that the problems for all variants are efficiently solvable for much larger graph classes. We present a polynomial-time algorithm for graphs of bounded clique-width. We also show that the problem is fixed-parameter tractable when parameterized by the vertex cover number. (C) 2017 Elsevier B.V. All rights reserved.

关键词： graph algorithm Alliance Clique-width Vertex cover

来源：评论

学校读者我要写书评

暂无评论

The Maximum Labeled Path Problem

引用

algorithmICA 2017年第1期78卷 298-318页

作者： Couetoux, Basile Nakache, Elie Vaxes, Yann Aix Marseille Univ CNRS LIF UMR 7279 F-13288 Marseille France

In this paper, we study the approximability of the Maximum Labeled Path problem: given a vertex-labeled directed acyclic graph D, find a path in D that collects a maximum number of distinct labels. For any epsilon > 0, we provide a polynomial time approximation algorithm that computes a solution of value at least OPT1-epsilon and a self-reduction showing that any constant ratio approximation algorithm for this problem can be converted into a PTAS. This last result, combined with the APX-hardness of the problem, shows that the problem cannot be approximated within any constant ratio unless P = NP.

关键词： graph algorithm Approximation algorithm Hardness of approximation Labels

来源：评论

学校读者我要写书评

暂无评论

Robustness of First- and Second-Order Consensus algorithms for a Noisy Scale-Free Small-World Koch Network

引用

IEEE TRANSACTIONS ON CONTROL SYSTEMS TECHNOLOGY 2017年第1期25卷 342-350页

作者： Yi, Yuhao Zhang, Zhongzhi Shan, Liren Chen, Guanrong Fudan Univ Sch Comp Sci Shanghai Key Lab Intelligent Informat Proc Shanghai 200433 Peoples R China City Univ Hong Kong Dept Elect Engn Hong Kong Hong Kong Peoples R China

In this brief, we study first- and second-order consensus algorithms for the scale-free small-world Koch network, where vertices are subject to white noise. We focus on three cases of consensus schemes: 1) first-order leaderless algorithm;2) first-order algorithm with a single leader;and 3) second-order leaderless algorithm. We are concerned with the coherence of the Koch network in the H-2 norm, which captures the level of agreement of vertices in face of stochastic disturbances. Based on the particular network construction, we derive explicit expressions of the coherence for all the three consensus algorithms, as well as their dependence on the network size. Particularly, for the first-order leader-follower model, we show that coherence relies on the shortest-path distance between the leader and the largest-degree vertices, as well as the degree of the leader. The asymptotic behaviors for coherence of the three consensus algorithms in Koch network behave differently from those associated with other networks lacking scale-free small-world features, indicating significant influences of the scale-free small-world topology on the performance of the consensus algorithms in noisy environments.

关键词： Distributed average consensus graph algorithm noise scale-free network small-world network

来源：评论

学校读者我要写书评

暂无评论

On the minimum routing cost clustered tree problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2017年第3期33卷 1106-1121页

作者： Lin, Chen-Wan Wu, Bang Ye Natl Chung Cheng Univ Chiayi 621 Taiwan

For an edge-weighted graph , in which the vertices are partitioned into k clusters , a spanning tree T of G is a clustered spanning tree if T can be cut into k subtrees by removing edges such that each subtree is a spanning tree for one cluster. In this paper, we show the inapproximability of finding a clustered spanning tree with minimum routing cost, where the routing cost is the total distance summed over all pairs of vertices. We present a 2-approximation for the case that the input is a complete weighted graph whose edge weights obey the triangle inequality. We also study a variant in which the objective function is the total distance summed over all pairs of vertices of different clusters. We show that the problem is polynomial-time solvable when the number of clusters k is 2 and NP-hard for . Finally, we propose a polynomial-time 2-approximation algorithm for the case of three clusters.

关键词： Approximation algorithm NP-hard Spanning tree graph algorithm

来源：评论

学校读者我要写书评

暂无评论

IPED2: Inheritance Path Based Pedigree Reconstruction algorithm for Complicated Pedigrees

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2017年第5期14卷 1094-1103页

作者： He, Dan Wang, Zhanyong Parida, Laxmi Eskin, Eleazar IBM Corp Thomas J Watson Res Yorktown Hts NY 10598 USA Univ Calif Los Angeles Los Angeles CA 90095 USA

Reconstruction of family trees, or pedigree reconstruction, for a group of individuals is a fundamental problem in genetics. The problem is known to be NP-hard even for datasets known to only contain siblings. Some recent methods have been developed to accurately and efficiently reconstruct pedigrees. These methods, however, still consider relatively simple pedigrees, for example, they are not able to handle half-sibling situations where a pair of individuals only share one parent. In this work, we propose an efficient method, IPED2, based on our previous work, which specifically targets reconstruction of complicated pedigrees that include half-siblings. We note that the presence of half-siblings makes the reconstruction problem significantly more challenging which is why previous methods exclude the possibility of half-siblings. We proposed a novel model as well as an efficient graph algorithm and experiments show that our algorithm achieves relatively accurate reconstruction. To our knowledge, this is the first method that is able to handle pedigree reconstruction from genotype data when half-sibling exists in any generation of the pedigree.

关键词： Pedigree reconstruction half-sibling inheritance path dynamic programming graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Narrow sieves for parameterized paths and packings

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2017年 87卷 119-139页

作者： Bjorklund, Andreas Husfeldt, Thore Kaski, Petteri Koivisto, Mikko Lund Univ Dept Comp Sci POB 118 SE-22100 Lund Sweden IT Univ Copenhagen DK-2300 Copenhagen Denmark Aalto Univ Dept Informat & Comp Sci HIIT POB 15400 FI-00076 Aalto Finland Univ Helsinki HIIT Dept Comp Sci POB 68 FI-00014 Helsinki Finland

We present parameterized algorithms for the k-path problem, the p-packing of q-sets problem, and the q-dimensional p-matching problem. Our algorithms solve these problems with high probability in time exponential only in the parameter (k, p, q) and using polynomial space. The constant bases of the exponentials are significantly smaller than in previous works;for example, for the k-path problem the improvement is from 2 to 1.66. We also show how to detect if a d-regular graph admits an edge coloring with d colors in time within a polynomial factor of 2((d-1)n/2). Our techniques generalize an algebraic approach studied in various recent works. (c) 2017 Elsevier Inc. All rights reserved.

关键词： Determinant Edge coloring graph algorithm k-Path Multidimensional matching Sieve Set packing Polynomial identity testing Randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Computational methods to identify metabolic sub-networks based on metabolomic profiles

引用

BRIEFINGS IN BIOINFORMATICS 2017年第1期18卷 43-56页

作者： Frainay, Clement Jourdan, Fabien Toulouse Univ INRA INP Res Ctr Food ToxicolUMR 1331 180 Chemin Tournefeuille F-31027 Toulouse France

Untargeted metabolomics makes it possible to identify compounds that undergo significant changes in concentration in different experimental conditions. The resulting metabolomic profile characterizes the perturbation concerned, but does not explain the underlying biochemical mechanisms. Bioinformatics methods make it possible to interpret results in light of the whole metabolism. This knowledge is modelled into a network, which can be mined using algorithms that originate in graph theory. These algorithms can extract sub-networks related to the compounds identified. Several attempts have been made to adapt them to obtain more biologically meaningful results. However, there is still no consensus on this kind of analysis of metabolic networks. This review presents the main graph approaches used to interpret metabolomic data using metabolic networks. Their advantages and drawbacks are discussed, and the impacts of their parameters are emphasized. We also provide some guidelines for relevant sub-network extraction and also suggest a range of applications for most methods.

关键词： metabolomics metabolic network graph algorithm path search sub-network extraction

来源：评论

学校读者我要写书评

暂无评论

An algorithm for Motif-Based Network Design

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2017年第5期14卷 1181-1186页

作者： Maki-Marttunen, Tuomo Tampere Univ Technol Dept Signal Proc Tampere 33720 Finland Univ Oslo Inst Clin Med N-0316 Oslo Norway

A determinant property of the structure of a biological network is the distribution of local connectivity patterns, i.e., network motifs. In this work, a method for creating directed, unweighted networks while promoting a certain combination of motifs is presented. This motif-based network algorithm starts with an empty graph and randomly connects the nodes by advancing or discouraging the formation of chosen motifs. The in-or out-degree distribution of the generated networks can be explicitly chosen. The algorithm is shown to perform well in producing networks with high occurrences of the targeted motifs, both ones consisting of three nodes as well as ones consisting of four nodes. Moreover, the algorithm can also be tuned to bring about global network characteristics found in many natural networks, such as small-worldness and modularity.

关键词： Network motifs network structure random attachment graph algorithm network generation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：