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

Improved algorithms and complexity results for power domination in graphs

ALGORITHMICA 2008年第2期52卷 177-202页

作者： Guo, Jiong Niedermeier, Rolf Raible, Daniel Univ Jena Inst Informat D-07743 Jena Germany Univ Trier Abt Informat Wirtschaftsinformat Fachbereich 4 D-54286 Trier Germany

The NP-complete POWER DOMINATING SET problem is an "electric power networks variant" of the classical domination problem in graphs: Given an undirected graph G = (V, E), find a minimum-size set P. V such that all vertices in V are "observed" by the vertices in P. Herein, a vertex observes itself and all its neighbors, and if an observed vertex has all but one of its neighbors observed, then the remaining neighbor becomes observed as well. We show that POWER DOMINATING SET can be solved by "bounded-treewidth dynamic programs." For treewidth being upper-bounded by a constant, we achieve a linear-time algorithm. In particular, we present a simplified linear-time algorithm for POWER DOMINATING SET in trees. Moreover, we simplify and extend several NP-completeness results, particularly showing that POWER DOMINATING SET remains NP-complete for planar graphs, for circle graphs, and for split graphs. Specifically, our improved reductions imply that POWER DOMINATING SET parameterized by vertical bar P vertical bar is W[2]-hard and it cannot be better approximated than DOMINATING SET.

关键词： design and analysis of algorithms computational complexity parameterized complexity fixed-parameter algorithms graph algorithms graphs of bounded treewidth (power) domination in graphs

来源：评论

学校读者我要写书评

暂无评论

A bounded search tree algorithm for parameterized FACE COVER

引用

JOURNAL OF DISCRETE algorithms 2008年第4期6卷 541-552页

作者： Abu-Khzam, Faisal N. Fernau, Henning Langston, Michael A. Lebanese Amer Univ Div Comp Sci & Math Beirut Lebanon Univ Trier Abt Informat FB 4 D-54286 Trier Germany Univ Tennessee Dept Comp Sci Knoxville TN 37996 USA

The parameterized complexity of the FACE COVER problem is considered. The input to this problem is a plane graph G with n vertices. The question asked is whether, for a given parameter value k, there exists a set of k or fewer faces whose boundaries collectively cover (contain) every vertex in G. Early attempts achieved run times of O*(12(k)) or worse, by reducing the problem into a special form of DOMINATING SET, namely RED-BLUE DOMINATING SET, restricted to planar graphs. Here, we consider a direct approach, where some surgical operation is performed on the graph at each branching decision. This paper builds on previous work of the authors and employs a structure theorem of Aksionov et al., with a detailed case analysis, to produce a FACE COVER algorithm that runs in O(4.6056(k) + n(2)) time. We also point to the tight connections with RED-BLUE DOMINATING SET on planar graphs via the annotated version of FACE COVER that we consider in our search tree algorithm. Hence, we get both a O(4.6056(k) + n(2)) time algorithm for solving RED-BLUE dominating SET on planar graphs and a polynomial time algorithm for producing a linear kernel for annotated face cover. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Plane graphs fixed-parameter algorithms Face cover Planar red-blue dominating set

来源：评论

学校读者我要写书评

暂无评论

Linearity of grid minors in treewidth with applications through bidimensionality

引用

COMBINATORICA 2008年第1期28卷 19-36页

作者： Demaine, Erik D. Hajiachayi, Mohammadtaghi MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA

We prove that any H-minor-free graph, for a fixed graph H, of treewidth w has ail Omega(w) x Omega(w) grid graph as a minor. Thus grid ininors suffice to certify that H-minor-free graphs have large treewidth, up to constant factors. This strong relationship was previously known for the special cases of planar graphs and bounded-genus graphs, and is known not to hold for general graphs. The approach of this paper can be viewed more generally as a framework for extending combinatorial results on planar graphs to hold on H-minor-free graphs for any fixed H. Our result has many combinatorial consequences on bidimensionality theory, parameter-treewidth bounds, separator theorems, and bounded local treewidth;each of these combinatorial results has several algorithmic consequences including subexponential fixed-parameter algorithms and approximation algorithms.

关键词： fixed-parameter algorithms SINGLE-CROSSING GRAPHS BOUNDED-GENUS GRAPHS PLANAR GRAPHS APPROXIMATION algorithms DOMINATING SET TREE-WIDTH DIAMETER FAMILIES THEOREM

来源：评论

学校读者我要写书评

暂无评论

Computational study on dominating set problem of planar graphs

引用

2nd International Conference on Combinatorial Optimization and Applications

作者： Marzban, Marjan Gu, Qian-Ping Jia, Xiaohua Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9783540850960

Recently, there has been significant theoretical progress towards fixed-parameter algorithms for the DOMINATING SET problem of planar graphs. It is known that the problem on a, planar graph with n vertices and dominating number k can be solved in O(c(root k)n) time using tree/branch-decomposition based algorithms, where c is some constant. However there has been no computational study report on the practical performances of the O(c(root k)n) time algorithms. In this paper, we report computational results of Fomin and Thilikos algorithm which uses the branch-decomposition based approach. The computational results show that the algorithm can solve the DOMINATING SET problem of large planar graphs in a practical time for the class of graphs with small branchwidth. For the class of graphs with large branchwidth, the size of instances that can be solved by the algorithm in a practical time is limited to a few hundreds edges. The practical performances of the algorithm coincide with the theoretical analysis of the algorithm. The results of this paper suggest that the branch-decomposition based algorithms can be practical for some applications on planar graphs.

关键词： PLANAR DOMINATING SET branch-decomposition fixed-parameter algorithms data reduction computational study

来源：评论

学校读者我要写书评

暂无评论

Ubiquitous parameterization - Invitation to fixed-parameter algorithms

引用

29th International Symposium on Mathematical Foundations of Computer Science

作者： Niedermeier, R Univ Tubingen Wilhelm Schickard Inst Informat D-72076 Tubingen Germany

ISBN: (纸本)3540228233

Problem parameters are ubiquitous. In every area of computer science, we find all kinds of "special aspects" to the problems encountered. Hence, the study of parameterized complexity for computationally hard problems is proving highly fruitful. The purpose of this article is to stir the reader's interest in this field by providing a gentle introduction to the rewarding field of fixed-paxameter algorithms.

关键词： NP-hardness parameterized complexity fixed-parameter algorithms parameterization

来源：评论

学校读者我要写书评

暂无评论

Haplotyping with missing data via perfect path phylogenies

引用

DISCRETE APPLIED MATHEMATICS 2007年第6-7期155卷 788-805页

作者： Gramm, Jens Nierhoff, Till Sharan, Roded Tantau, Till Med Univ Lubeck Inst Theoret Informat D-23538 Lubeck Germany Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel Int Comp Sci Inst Berkeley CA 94704 USA Univ Tubingen Wilhelm Schickard Inst Informat D-72074 Tubingen Germany

Computational methods for inferring haplotype information from genotype data are used in studying the association between genomic variation and medical condition. Recently, Gusfield proposed a haplotype inference method that is based on perfect phylogeny principles. A fundamental problem arises when one tries to apply this approach in the presence of missing genotype data, which is common in practice. We show that the resulting theoretical problem is NP-hard even in very restricted cases. To cope with missing data, we introduce a variant of haplotyping via perfect phylogeny in which a path phylogeny is Sought. Searching for perfect path phylogenies is strongly motivated by the characteristics of human genotype data: 70% of real instances that admit a perfect phylogeny also admit a perfect path phylogeny. Our main result is a fixed-parameter algorithm for haplotyping with missing data via perfect path phylogenies. We also present a simple linear-time algorithm for the problem on complete data. (c) 2006 Elsevier B.V. All rights reserved.

关键词： haplotyping haplotypes genotypes missing data incomplete data phylogenetics perfect phylogenies path phylogenies fixed-parameter algorithms

来源：评论

学校读者我要写书评

暂无评论

Configurations with few crossings in topological graphs

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2007年第2期37卷 104-114页

作者： Knauer, Christian Schramm, Etienne Spillner, Andreas Wolff, Alexander Free Univ Berlin Inst Comp Sci Berlin Germany Univ Karlsruhe Fak Informat D-76128 Karlsruhe Germany Univ Jena Inst Comp Sci Jena Germany

In this paper we study the problem of computing subgraphs of a certain configuration in a given topological graph G such that the number of crossings in the subgraph is minimum. The configurations that we consider are spanning trees, s-t paths, cycles, matchings, and kappa-factors for kappa is an element of {1, 2). We show that it is NP-hard to approximate the minimum number of crossings for these configurations within a factor of k(1 - epsilon) for any epsilon > 0, where k is the number of crossings in G. We then give a simple fixed-parameter algorithm that tests in O*(2(k)) time whether G has a crossing-free configuration for any of the above, where the O*-notation neglects polynomial terms. For some configurations we have faster algorithms. The respective running times are O*(1.9999992(k)) for spanning trees and O*((root 3)(k)) for s-t paths and cycles. For spanning trees we also have an O*(1.968k)-time Monte-Carlo algorithm. Each. O*(beta(k))-time decision algorithm can be turned into an O*((beta + 1)(k))-time optimization algorithm that computes a configuration with the minimum number of crossings. (c) 2006 Elsevier B.V. All rights reserved.

关键词： topological graphs crossing minimization non-approximability approximation algorithms fixed-parameter algorithms Monte-Carlo algorithms

来源：评论

学校读者我要写书评

暂无评论

Determining the smallest k such that G is k-outerplanar

Determining the smallest k such that G is k...

引用

15th Annual European Symposium on algorithms (ESA 2007)

作者： Kammer, Frank Univ Augsburg Inst Informat D-86135 Augsburg Germany

ISBN: (纸本)9783540755197

The outerplanarity index of a planar graph G is the smallest k such that G has a k-outerplanar embedding. We show how to compute the outerplanarity index of an P.-vertex planar graph in O(n(2)) time, improving the previous best bound of O(k(3)n(2)). Using simple variations of the computation we can determine the radius of a planar graph in O(n(2)) time and its depth in O(n(3)) time. We also give a linear-time 4-approximation algorithm for the outerplanarity index and show how it can be used to solve maximum independent set and several other NP-hard problems faster on planar graphs with outerplanarity index within a constant factor of their treewidth.

关键词： outerplanarity index k-outerplanar fixed-parameter algorithms NP-hard SPQR trees

来源：评论

学校读者我要写书评

暂无评论

Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs

引用

JOURNAL OF THE ACM 2005年第6期52卷 866-893页

作者： Demaine, ED Fomin, FV Hajiaghayi, M Thilikos, DM MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA Univ Bergen Dept Informat N-5020 Bergen Norway MIT Cambridge MA 02139 USA Natl & Capodistrian Univ Athens Dept Math GR-15784 Athens Greece

We introduce a new framework for designing fixed-parameter algorithms with subexponential running time-2(O(root k))n(O(1)). Our results apply to a broad family of graph problems, called bidimensional problems, which includes many domination and problems such as vertex cover, feedback vertex set, minimum maximal matching, dominating set, edge dominating set, disk dimension, and many others restricted to bounded-genus graphs (phrased as bipartite-graph problem). Furthermore, it is fairly straightforward to prove that a problem is bidimensional. In particular, our framework includes, as special cases, all previously known problems to have such subexponential algorithms. Previously, these algorithms applied to planar graphs, single-crossing-minor-free graphs, and/or map graphs;we extend these results to apply to bounded-genus graphs as well. In a parallel development of combinatorial results, we establish an upper bound on the treewidth (or branchwidth) of a bounded-genus graph that excludes some planar graph H as a minor. This bound depends linearly on the size vertical bar V(H)vertical bar of the excluded graph H and the genus g(G) of the graph G, and applies and extends the graph-minors work of Robertson and Seymour. Building on these results, we develop subexponential fixed-parameter algorithms for dominating set, vertex cover, and set cover in any class of graphs excluding a fixed graph H as a minor. In particular, this general category of graphs includes planar graphs, bounded-genus graphs, single-crossing-minor-free graphs, and any class of graphs that is closed under taking minors. Specifically, the running time is 2(O(root k))n(h), where h is a constant depending only on H, which is polynomial for k = O(log(2) n). We introduce a general approach for developing algorithms on H-minor-free graphs, based on structural results about H-minor-free graphs at the heart of Robertson and Seymour's graph-minors work. We believe this approach opens the way to further develo

关键词： algorithms design theory (k, r)-center fixed-parameter algorithms domination planar graph map graph

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：