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

On the complexity of reconfiguration problems

THEORETICAL COMPUTER SCIENCE 2011年第12-14期412卷 1054-1065页

作者： Ito, Takehiro Demaine, Erik D. Harvey, Nicholas J. A. Papadimitriou, Christos H. Sideri, Martha Uehara, Ryuhei Uno, Yushi Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada Univ Calif Berkeley Div Comp Sci Dept EECS Berkeley CA 94720 USA Athens Univ Econ & Business Dept Comp Sci Athens 10434 Greece JAIST Sch Informat Sci Nomi Ishikawa 9231292 Japan Osaka Prefecture Univ Grad Sch Sci Naka Ku Sakai Osaka 5998531 Japan

Reconfiguration problems arise when we wish to find a step-by-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible. We demonstrate that a host of reconfiguration problems derived from NP-complete problems are PSPACE-complete, while some are also NP-hard to approximate. In contrast, several reconfiguration versions of problems in P are solvable in polynomial time. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Approximation graph algorithm PSPACE-complete Reachability on solution space

来源：评论

学校读者我要写书评

暂无评论

Linear-time algorithm for the matched-domination problem in cographs

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2011年第10期88卷 2042-2056页

作者： Hung, Ruo-Wei Yao, Chih-Chia Chaoyang Univ Technol Dept Comp Sci & Informat Engn Taichung 41349 Taiwan

Let G = (V, E) be a graph without isolated vertices. A matching in G is a set of independent edges in G. A perfect matching M in G is a matching such that every vertex of G is incident to an edge of M. A set S subset of V is a paired-dominating set of G if every vertex not in S is adjacent to a vertex in S and if the subgraph induced by S contains a perfect matching. The paired-domination problem is to find a paired-dominating set of G with minimum cardinality. This paper introduces a generalization of the paired-domination problem, namely, the matched-domination problem, in which some constrained vertices are in paired-dominating sets as far as they can. Further, possible applications are also presented. We then present a linear-time constructive algorithm to solve the matched-domination problem in cographs.

关键词： graph algorithm paired-domination constrained vertex set matched-domination cographs

来源：评论

学校读者我要写书评

暂无评论

PARAMETERIZED COMPLEXITY OF ARC-WEIGHTED DIRECTED STEINER PROBLEMS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2011年第2期25卷 583-599页

作者： Guo, Jiong Niedermeier, Rolf Suchy, Ondrej Univ Saarland D-66123 Saarbrucken Germany TU Berlin Inst Softwaretech & Theoret Informat D-10587 Berlin Germany Charles Univ Prague Dept Appl Math KAM CR-11800 Prague Czech Republic Charles Univ Prague Inst Theoret Comp Sci ITI CR-11800 Prague Czech Republic

We start a systematic parameterized computational complexity study of three NP-hard network design problems on arc-weighted directed graphs: directed Steiner tree, strongly connected Steiner subgraph, and directed Steiner network. We investigate their parameterized complexities with respect to the three parameterizations: "number of terminals," "an upper bound on the size of the connecting network," and the combination of these two. We achieve several parameterized hardness results as well as some fixed-parameter tractability results, in this way extending previous results of Feldman and Ruhl [SIAM J. Comput., 36 (2006), pp. 543-561].

关键词： computational intractability W[1]-hardness W[2]-hardness fixed-parameter tractability problem kernel graph algorithm network design

来源：评论

学校读者我要写书评

暂无评论

Generation of Symmetric and Asymmetric Biconnected Rooted Outerplanar graphs

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2011年第2期E94D卷 211-219页

作者： Zhuang, Bingbing Nagamochi, Hiroshi Kyoto Univ Dept Appl Math & Phys Grad Sch Informat Kyoto 6068501 Japan

In a rooted graph, a vertex is designated as its root. An outerplanar graph is represented by a plane embedding such that all vertices appear along its outer boundary. Two different plane embeddings of a rooted outerplanar graphs are called symmetric copies. Given integers n >= 3 and g >= 3, we give an O(n)-space and O(1)-time delay algorithm that generates all biconnected rooted outerplanar graphs with exactly n vertices such that the size of each inner face is at most g without delivering two symmetric copies of the same graph.

关键词： enumeration algorithm graph algorithm planar graph outerplanar graph symmetry

来源：评论

学校读者我要写书评

暂无评论

On acyclic edge coloring of toroidal graphs

引用

INFORMATION PROCESSING LETTERS 2011年第13期111卷 647-649页

作者： Xu, Yian Nanjing Normal Univ Sch Math Sci Nanjing 210046 Peoples R China

Let c be a proper edge coloring of a graph G. If there exists no bicolored cycle in G with respect to c, then c is called an acyclic edge coloring of G. Let G be a planar graph with maximum degree Delta and girth g. In Dong and Xu (2010) [8], Dong and Xu proved that G admits an acyclic edge coloring with Delta(G) colors if Delta >= 8 and g >= 7, or Delta >= 6 and g >= 8, or Delta >= 5 and g >= 9, or Delta >= 4 and g >= 10, or Delta >= 3 and g >= 14. In this note, we fix a small gap in the proof of Dong and Xu (2010) [8], and generalize the above results to toroidal graphs. (C) 2011 Elsevier B.V. All rights reserved.

关键词： graph algorithm Acyclic edge coloring Maximum degree Toroidal graphs

来源：评论

学校读者我要写书评

暂无评论

Maximum bipartite flow in networks with adaptive channel width

引用

THEORETICAL COMPUTER SCIENCE 2011年第24期412卷 2577-2587页

作者： Azar, Yossi Madry, Aleksander Moscibroda, Thomas Panigrahi, Debmalya Srinivasan, Aravind MIT Comp Sci & Artificial Intelligence Lab Stata Ctr Cambridge MA 02139 USA Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel Univ Maryland Dept Comp Sci College Pk MD 20742 USA Univ Maryland Inst Adv Comp Studies College Pk MD 20742 USA Microsoft Res Redmond WA 98052 USA

Traditionally, network optimization problems assume that each link in the network has a fixed capacity. Recent research in wireless networking has shown that it is possible to design networks where the capacity of the links can be changed adaptively to suit the needs of specific applications. In particular, one gets a choice of having a few high capacity outgoing links or many low capacity ones at any node of the network. This motivates us to have a re-look at classical network optimization problems and design algorithms to solve them in this new framework. In particular, we consider the problem of maximum bipartite flow, which has been studied extensively in the fixed-capacity network model. One of the motivations for studying this problem arises from the need to maximize the throughput of an infrastructure wireless network comprising base-stations (one set of vertices in the bipartition) and clients (the other set of vertices in the bipartition). We show that this problem has a significantly different combinatorial structure in this new network model from the fixed-capacity one. While there are several polynomial time algorithms for the maximum bipartite flow problem in traditional networks, we show that the problem is NP-hard in the new model. In fact, our proof extends to showing that the problem is APX-hard. we complement our lower bound by giving two algorithms for solving the problem approximately. The first algorithm is deterministic and achieves an approximation factor of O(log N), where N is the number of nodes in the network, while the second algorithm is randomized and achieves an approximation factor of e/e-1. (C) 2010 Elsevier B.V. All rights reserved.

关键词： graph algorithm Maximum flow Linear program rounding Wireless networks Adaptive channel width

来源：评论

学校读者我要写书评

暂无评论

AN APPLICATION OF ST-NUMBERING TO SECRET KEY AGREEMENT

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2011年第5期22卷 1211-1227页

作者： Mizuki, Takaaki Nakayama, Satoru Sone, Hideaki Tohoku Univ Cybersci Ctr Aoba Ku Sendai Miyagi 9808578 Japan Tohoku Univ Grad Sch Informat Sci Sone Lab Aoba Ku Sendai Miyagi 9808578 Japan

Assume that there are players and an eavesdropper Eve, where several pairs of players have shared secret keys beforehand. We regard each player as a vertex of a graph and regard each pair of players sharing a key as an edge. Consider the case where Eve knows some of the keys according to a certain probability distribution. In this paper, applying the technique of st-numbering, we propose a protocol which allows any two designated players to agree on a secret key through such a "partially leaked key exchange graph." Our protocol is optimal in the sense that Eve's knowledge about the secret key agreed on by the two players is as small as possible.

关键词： graph algorithm st-numbering Key sharing graph Key agreement protocol Information-theoretic secrecy

来源：评论

学校读者我要写书评

暂无评论

GreedyMAX-type algorithms for the Maximum Independent Set Problem

GreedyMAX-type Algorithms for the Maximum Independent Set Pr...

引用

37th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2011

作者： Borowiecki, Piotr Goering, Frank Gdansk Univ Technol Dept Algorithms & Syst Modeling Fac Elect Telecommun & Informat Narutowicza 11-12 PL-80233 Gdansk Poland Fak Math D-09107 Chemnitz Germany

ISBN: (纸本)9783642183805

A maximum independent set problem for a simple graph G = (V, E) is to find the largest subset of pairwise nonadjacent vertices. The problem is known to be NP-hard and it is also hard to approximate. Within this article we introduce a non-negative integer valued function p defined on the vertex set V(G) and called a potential function of a graph G, while P(G) = max(upsilon is an element of v(G))p(upsilon) is called a potential of G. For any graph P(G) <= Delta(G), where Delta(G) is the maximum degree of G. Moreover, Delta(G) - Delta(G) may be arbitrarily large. A potential of a vertex lets us get a closer insight into the properties of its neighborhood which leads to the definition of the family of GreedyMAX-type algorithms having the classical GreedyMAX algorithm as their origin. We establish a lower bound 1/(P + 1) for the performance ratio of GreedyMAX-type algorithms which favorably compares with the bound 1/(Delta + 1) known to hold for GreedyMAX. The cardinality of an independent set generated by any GreedyMAX-type algorithm is at least Sigma(upsilon is an element of v(G))(p(upsilon) + 1)(-1), which strengthens the bounds of Turin and Caro-Wei stated in terms of vertex degrees.

关键词： independent set stable set graph algorithm greedy algorithm ordering potential of a graph

来源：评论

学校读者我要写书评

暂无评论

Maximum bipartite flow in networks with adaptive channel width

Maximum bipartite flow in networks with adaptive channel wid...

引用

36th International Colloquium on Automata, Languages and Programming

ISBN: (纸本)3642029299

关键词： graph algorithm Maximum flow Linear program rounding Wireless networks Adaptive channel width

来源：评论

学校读者我要写书评

暂无评论

A novel method for deployment of distributed network monitors

A novel method for deployment of distributed network monitor...

引用

4th International Conference on Information Management, Innovation Management and Industrial Engineering, ICIII 2011

作者： Ou, Peng Li, Zhishu Lin, Xun School of Computer Science Sichuan University Chengdu China School of Economic Information Engineering Southwest University of Finance and Economy Chengdu China

ISBN: (纸本)9780769545233

The requirement of increasing the deployment of a distributed monitoring system as the network expanding is becoming a new research focus. The problem is where to put those monitors and by how much to put. This paper analyses the monitors adding mechanism and present a novel algorithm for finding candidate locations for additional deployment in the network. The algorithm is based on Apriori search method that combines with the link weight change algorithm. We also develop the greedy algorithm with Group Betweenness Centrality(GBC) involved for the purpose of comparing. The result shows that the new algorithm need less additional monitors than greedy algorithm, thus is useful for network monitors deployment. © 2011 IEEE.

关键词： algorithm design and analysis Apriori search method Distributed System Educational institutions graph algorithm Greedy algorithms Group Betweenness Inference algorithms Measurement Monitoring Network Centrality Routing distributed monitoring system distri

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：