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

linear-time algorithms for computing the reliability of bipartite and (# ≤ 2) star distributed computing systems

COMPUTERS & OPERATIONS RESEARCH 2003年第11期30卷 1697-1712页

作者： Lin, MS Natl Taipei Univ Technol Dept Elect Engn Taipei 106 Taiwan

Let S = (V,F) denote a distributed computing system with star topology, where V is the set of nodes of S and F is the set of files distributed in V. The problem of computing the reliability of S has been shown to be #P-complete. Therefore, all known exact algorithms for this problem have exponential time complexity. This study presents two linear-time algorithms to compute the reliability of two restricted subclasses of S. The first algorithm runs in O(\F\) when the file distribution is limited to being bipartite and non-separable. The second algorithm runs in O(\V\), when each file is allocated to at most two distinct nodes and each node contains at most two distinct records. If the failure and working probabilities of every node are identical, then the computation can be accelerated to O(log(\V\)) time by means of the Fibonacci number and the Lucas number.

关键词： reliability distributed computing systems #P-complete linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs

引用

THEORETICAL COMPUTER SCIENCE 2005年第1-3期341卷 411-440页

作者： Hung, RW Chang, MS Natl Chung Cheng Univ Dept Comp Sci & Informat Engn Chiayi 621 Taiwan

A Hamiltonian path of a graph G is a simple path that contains each vertex of G exactly once. A Hamiltonian cycle of a graph is a simple cycle with the same property. The Hamiltonian path (resp. cycle) problem involves testing whether a Hamiltonian path (resp. cycle) exists in a graph. The 1HP (resp. 2HP) problem is to determine whether a graph has a Hamiltonian path starting from a specified vertex (resp. starting from a specified vertex and ending at the other specified vertex). The Hamiltonian problems include the Hamiltonian path, Hamiltonian cycle, 1HP, and 2HP problems. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. In this paper, we present a unified approach to solving the Hamiltonian problems on distance-hereditary graphs in linear time. (c) 2005 Elsevier B.V. All rights reserved.

关键词： graph algorithms linear-time algorithms Hamiltonian problems distance-hereditary graphs

来源：评论

学校读者我要写书评

暂无评论

Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions

引用

THEORETICAL COMPUTER SCIENCE 2009年第1期410卷 1-15页

作者： Heggernes, Pinar Papadopoulos, Charis Univ Bergen Dept Informat N-5020 Bergen Norway

We study graph properties that admit an increasing, or equivalently decreasing, sequence of graphs on the same vertex set such that for any two consecutive graphs in the sequence their difference is a single edge. This is useful for characterizing and computing minimal completions and deletions of arbitrary graphs into having these properties. We prove that threshold graphs and chain graphs admit such sequences. Based on this characterization and other structural properties, we present linear-time algorithms both for computing minimal completions and deletions into threshold, chain, and bipartite graphs, and for extracting a minimal completion or deletion from a given completion or deletion. Minimum completions and deletions into these classes are NP-hard to compute. (C) 2008 Published by Elsevier B.V.

关键词： linear-time algorithms Minimal completions of graphs Minimal deletions of graphs Graph classes

来源：评论

学校读者我要写书评

暂无评论

linear Kernels and linear-time algorithms for Finding Large Cuts

引用

ALGORITHMICA 2018年第9期80卷 2574-2615页

作者： Etscheid, Michael Mnich, Matthias Univ Bonn Inst Informat Bonn Germany Maastricht Univ Dept Quantitat Econ Maastricht Netherlands

The maximum cut problem in graphs and its generalizations are fundamental combinatorial problems. Several of these cut problems were recently shown to be fixed-parameter tractable and admit polynomial kernels when parameterized above the tight lower bound measured by the size and order of the graph. In this paper we continue this line of research and considerably improve several of those results:We show that an algorithm by Crowston et al. (Algorithmica 72(3):734-757, 2015) for (Signed) Max-Cut Above Edwards-Erd A s Bound can be implemented so as to run in linear time;this significantly improves the previous analysis with run time . We give an asymptotically optimal kernel for (Signed) Max-Cut Above Edwards-Erd A s Bound with O(k) vertices, improving a kernel with vertices by Crowston et al. (Theor Comput Sci 513:53-64, 2013). We improve all known kernels for parameterizations above strongly -extendible properties (a generalization of the Max-Cut results) by Crowston et al. (Proceedings of FSTTCS 2013, Leibniz international proceedings in informatics, Guwahati, 2013) from vertices to O(k) vertices. Therefore, Max Acyclic Subdigraph parameterized above Poljak-Turzik bound admits a kernel with O(k) vertices and can be solved in time;this answers an open question by Crowston et al. (Proceedings of FSTTCS 2012, Leibniz international proceedings in informatics, Hyderabad, 2012).

关键词： Max-cut Kernelization linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

AUTOMATIC-GENERATION OF linear-time algorithms FROM PREDICATE CALCULUS DESCRIPTIONS OF PROBLEMS ON RECURSIVELY CONSTRUCTED GRAPH FAMILIES

引用

ALGORITHMICA 1992年第5-6期7卷 555-581页

作者： BORIE, RB PARKER, RG TOVEY, CA GEORGIA INST TECHNOL SCH INFORMAT & COMP SCIATLANTAGA 30332 GEORGIA INST TECHNOL SCH IND & SYST ENGNATLANTAGA 30332

This paper describes a predicate calculus in which graph problems can be expressed. Any problem possessing such an expression can be solved in linear time on any recursively constructed graph, once its decomposition tree is known. Moreover, the linear-time algorithm can be generated automatically from the expression, because all our theorems are proved constructively. The calculus is founded upon a short list of particularly primitive predicates, which in turn are combined by fundamental logical operations. This framework is rich enough to include the vast majority of known linear-time solvable problems. We have obtained these results independently of similar results by Courcelle [11], [12], through utilization of the framework of Bern et al. [6]. We believe our formalism is more practical for programmers who would implement the automatic generation machinery, and more readily understood by many theorists.

关键词： linear-time algorithms RECURSIVE GRAPH CLASS AUTOMATIC ALGORITHM GENERATION

来源：评论

学校读者我要写书评

暂无评论

Simple linear-time algorithms for counting independent sets in distance-hereditary graphs

引用

DISCRETE APPLIED MATHEMATICS 2018年 239卷 144-153页

作者： Lin, Min-Sheng Natl Taipei Univ Technol Dept Elect Engn Taipei 106 Taiwan

A connected graph is distance-hereditary if any two vertices have the same distance in all of its connected induced subgraphs. This paper proposes a unified method for designing linear-time algorithms for counting independent sets and their two variants, independent dominating sets and independent perfect dominating sets, in distance-hereditary graphs. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Distance-hereditary graphs Counting problem Independent sets Independent dominating sets Independent perfect dominating sets linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Solving NP-hard problems on GATEx graphs: linear-time algorithms for perfect orderings, cliques, colorings, and independent sets

引用

THEORETICAL COMPUTER SCIENCE 2024年 1037卷

作者： Hellmuth, Marc Scholz, Guillaume E. Stockholm Univ Fac Sci Dept Math SE-10691 Stockholm Sweden Univ Leipzig Dept Comp Sci & Interdisciplinary Bioinformat Grp Hartelstr 16-18 D-04107 Leipzig Germany Univ Leipzig Interdisciplinary Ctr Bioinformat Hartelstr 16-18 D-04107 Leipzig Germany

The class of GAlled-Tree Explainable (GATEx) graphs has recently been discovered as a natural generalization of cographs. Cographs are precisely those graphs that can be uniquely represented by a rooted tree where the leaves correspond to the vertices of the graph. As a generalization, GATEx graphs are precisely those that can be uniquely represented by a particular rooted acyclic network, called a galled-tree. This paper explores the use of galled-trees to solve combinatorial problems on GATEx graphs that are, in general, NP-hard. We demonstrate that finding a maximum clique, an optimal vertex coloring, a perfect order, as well as a maximum independent set in GATEx graphs can be efficiently done in linear time. The key idea behind the linear-time algorithms is to utilize the galled-trees that explain the GATEx graphs as a guide for computing the respective cliques, colorings, perfect orders, or independent sets.

关键词： Modular decomposition Galled-tree Cograph NP-hard problems linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

A linear-time ALGORITHM FOR FINDING A SPARSE K-CONNECTED SPANNING SUBGRAPH OF A K-CONNECTED GRAPH

引用

ALGORITHMICA 1992年第5-6期7卷 583-596页

作者： NAGAMOCHI, H IBARAKI, T 1. Department of Applied “Mathematics and Physics Faculty of Engineering Kyoto University 606 Kyoto Japan

We show that any k-connected graph G = (V, E) has a sparse k-connected spanning subgraph G' = (V, E') with \E'\ = O(k\V\) by presenting an O(\E\)-time algorithm to find one such subgraph, where connectivity stands for either edge-connectivity or node-connectivity. By using this algorithm as preprocessing, the time complexities of some graph problems related to connectivity can be improved. For example, the current best time bound O(max{k2\V\1/2, k\V\}\E\) to determine whether node-connectivity kappa(G) of a graph G = (V, E) is larger than a given integer k or not can be reduced to O(max{k3\V\3/2, k2\V\2}).

关键词： UNDIRECTED GRAPHS SPANNING SUBGRAPHS CONNECTIVITY K-EDGE-CONNECTIVITY K-NODE-CONNECTIVITY linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

A linear-time algorithm for the k-fixed-endpoint path cover problem on cographs

引用

NETWORKS 2007年第4期50卷 231-240页

作者： Asdre, Katerina Nikolopoulos, Stavros D. Univ Ioannina Dept Comp Sci GR-45110 Ioannina Greece

In this paper, we study a variant of the path cover problem, namely, the k-fixed-endpoint path cover problem. Given a graph G and a subset T of k vertices of V(G), a k-fixed-endpoint path cover of G with respect to T is a set of vertex-disjoint paths P that covers the vertices of G such that the k vertices of T are all endpoints of the paths in P. The k-fixed-endpoint path cover problem is to find a k-fixed-endpoint path cover of G of minimum cardinality;note that, if T is empty, that is, k = 0, the stated problem coincides with the classical path cover problem. We show that the k-fixed-endpoint path cover problem can be solved in linear time on the class of cographs. More precisely, we first establish a lower bound on the size of a minimum k-fixed-endpoint path cover of a cograph and prove structural properties for the paths of such a path cover. Then, based on these properties, we describe an algorithm which, for a cograph G on n vertices and m edges, computes a minimum k-fixed-endpoint path cover of G in linear time, that is, in O(n + m) time. The proposed algorithm is simple, requires linear space, and also enables us to solve some path cover related problems, such as the 1 HIP and 2HP, on cographs within the same time and space complexity. (c) 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(4), 231-240 2007

关键词： perfect graphs complement reducible graphs cographs cotree path cover fixed-endpoint path cover linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

linear-time encodable/decodable codes with near-optimal rate

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2005年第10期51卷 3393-3400页

作者： Guruswami, V Indyk, P Univ Washington Dept Comp Sci & Engn Seattle WA 98195 USA MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA

We present an explicit construction of linear-time encodable and decodable codes of rate r which can correct a,fraction (1 - r - epsilon)/2 of errors over an alphabet of constant size depending only on E, for every 0 < r < 1 and arbitrarily small epsilon > 0. The error-correction performance of these codes is optimal as seen by the Singleton bound (these are "near-MDS" codes). Such near-MDS linear-time codes were known for the decoding from erasures;our construction generalizes this to handle errors as well. Concatenating these codes with good, constant-sized binary codes gives a construction of linear-time binary codes which meet the Zyablov bound, and also the more general Blokh-Zyablov bound (by resorting to multilevel concatenation). Our work also yields linear-time encodable/decodable codes which match Forney's error exponent for concatenated codes for communication over the binary symmetric channel. The encoding/decoding complexity was quadratic in Forney's result, and Forney's bound has remained the best constructive error exponent for almost 40 years now. In summary, our results match the performance of the previously known explicit constructions of codes that had polynomial time encoding and decoding, but in 1 addition have linear-time encoding and decoding algorithms.

关键词： expander graphs Forney's error exponent iterative decoding linear-time algorithms MDS codes Singleton bound Zyablov bound

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：