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

A Simple linear-time Recognition Algorithm for Weakly Quasi-Threshold Graphs

GRAPHS AND COMBINATORICS 2011年第4期27卷 557-565页

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

Weakly quasi-threshold graphs form a proper subclass of the well-known class of cographs by restricting the join operation. In this paper we characterize weakly quasi-threshold graphs by a finite set of forbidden subgraphs: the class of weakly quasi-threshold graphs coincides with the class of {P-4, co-(2P(3))}-free graphs. Moreover we give the first linear-time algorithm to decide whether a given graph belongs to the class of weakly quasi-threshold graphs, improving the previously known running time. Based on the simplicity of our recognition algorithm, we can provide certificates of membership (a structure that characterizes weakly quasi-threshold graphs) or non-membership (forbidden induced subgraphs) in additional O(n) time. Furthermore we give a linear-time algorithm for finding the largest induced weakly quasi-threshold subgraph in a cograph.

关键词： Weakly quasi-threshold graphs Cographs Forbidden induced subgraphs Recognition linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

A polynomial solution to the k-fixed-endpoint path cover problem on proper interval graphs

引用

THEORETICAL COMPUTER SCIENCE 2010年第7-9期411卷 967-975页

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

We study a variant of the path cover problem, namely, the k-fixed-endpoint path cover problem, or kPC for short. 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 kPC problem is to find a k-fixed-endpoint path cover of G of minimum cardinality;note that, if T is empty (or, equivalently, k = 0), the stated problem coincides with the classical path cover problem. The kPC problem generalizes some path cover related problems, such as the 1HP and 2HP problems, which have been proved to be NP-complete. Note that the complexity status for both 1HP and 2HP problems on interval graphs remains an open question (Damaschke ( 1993)[9]). In this paper, we show that the kPC problem can be solved in linear time on the class of proper interval graphs, that is, in O(n + m) time on a proper interval graph on n vertices and m edges. The proposed algorithm is simple, requires linear space. and also enables us to solve the 1HP and 2HP problems on proper interval graphs within the same time and space complexity. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Perfect graphs Proper interval graphs Path cover Fixed-endpoint path cover linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

The 1-Fixed-Endpoint Path Cover Problem is Polynomial on Interval Graphs

引用

ALGORITHMICA 2010年第3期58卷 679-710页

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

We consider a variant of the path cover problem, namely, the k-fixed-endpoint path cover problem, or kPC for short, on interval graphs. 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 kPC problem is to find a k-fixed-endpoint path cover of G of minimum cardinality;note that, if T is empty the stated problem coincides with the classical path cover problem. In this paper, we study the 1-fixed-endpoint path cover problem on interval graphs, or 1PC for short, generalizing the 1HP problem which has been proved to be NP-complete even for small classes of graphs. Motivated by a work of Damaschke (Discrete Math. 112: 4964, 1993), where he left both 1HP and 2HP problems open for the class of interval graphs, we show that the 1PC problem can be solved in polynomial time on the class of interval graphs. We propose a polynomial-time algorithm for the problem, which also enables us to solve the 1HP problem on interval graphs within the same time and space complexity.

关键词： Perfect graphs Interval graphs Path cover Fixed-endpoint path cover linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Characterizing and computing minimal cograph completions

引用

DISCRETE APPLIED MATHEMATICS 2010年第7期158卷 755-764页

作者： Lokshtanov, Daniel Mancini, Federico Papadopoulos, Charis Univ Bergen Dept Informat N-5020 Bergen Norway

A cograph completion of an arbitrary graph G is a cograph supergraph of G on the same vertex set. Such a completion is called minimal if the set of edges added to G is inclusion minimal. In this paper we present two results on minimal cograph completions. The first is a characterization that allows us to check in linear time whether a given cograph completion is minimal. The second result is a vertex incremental algorithm to compute a minimal cograph completion H of an arbitrary input graph G in O(vertical bar V(H)vertical bar + vertical bar E(H)vertical bar) time. An extended abstract of the result has been already presented at FAW 2008 [D. Lokshtanov, F. Mancini, C. Papadopoulos, Characterizing and computing minimal cograph completions, ill: Proceedings of FAW'08-2nd International Frontiers of Algorithmics Workshop, in: LNCS, vol. 5059, 2008, pp. 147-158. [1]]. (c) 2009 Elsevier B.V. All rights reserved.

关键词： Minimal completions Cographs linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity

Polylogarithmic Approximation for Edit Distance and the Asym...

引用

IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS)

作者： Andoni, Alexandr Krauthgamer, Robert Onak, Krzysztof Princeton Univ CCI Princeton NJ 08544 USA

ISBN: (纸本)9780769542447

We present a near-linear time algorithm that approximates the edit distance between two strings within a polylogarithmic factor. For strings of length n and every fixed epsilon > 0, the algorithm computes a (log n)(O(1/epsilon)) approximation in n(1+epsilon) time. This is an exponential improvement over the previously known approximation factor, 2((O) over tilde(root log n)), with a comparable running time [Ostrovsky and Rabani, J. ACM 2007;Andoni and Onak, STOC 2009]. This result arises naturally in the study of a new asymmetric query model. In this model, the input consists of two strings x and y, and an algorithm can access y in an unrestricted manner, while being charged for querying every symbol of x. Indeed, we obtain our main result by designing an algorithm that makes a small number of queries in this model. We then provide a nearly-matching lower bound on the number of queries. Our lower bound is the first to expose hardness of edit distance stemming from the input strings being "repetitive", which means that many of their substrings are approximately identical. Consequently, our lower bound provides the first rigorous separation between edit distance and Ulam distance.

关键词： edit distance sampling query complexity linear-time algorithms sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

A linear-time ALGORITHM FOR THE RESTRICTED PAIRED-DOMINATION PROBLEM IN COGRAPHS

引用

INTERNATIONAL JOURNAL OF INNOVATIVE COMPUTING INFORMATION AND CONTROL 2010年第11期6卷 4957-4978页

作者： Hung, Ruo-Wei 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 2,5 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 restricted paired domination problem, where some vertices are restricted so as to be in paired dominating sets Further, possible applications are also presented We then present a linear-time constructive algorithm to solve the restricted paired domination problem in cographs

关键词： Graph algorithms linear-time algorithms Paired-domination Restricted paired-domination Cographs

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A linear-time Algorithm for Broadcast Domination in a Tree

引用

NETWORKS 2009年第2期53卷 160-169页

作者： Dabney, John Dean, Brian C. Hedetniemi, Stephen T. Clemson Univ Sch Comp Clemson SC 29634 USA

The broadcast domination problem is a variant of the classical minimum dominating set problem in which a transmitter of power p at vertex v is capable of dominating (broadcasting to) all vertices within distance p from v. Our goal is to assign a broadcast power f(v) to every vertex v in a graph such that Sigma(v is an element of v) f(v) is minimized, and such that every vertex u with f(u) = 0 Is within distance f(v) of some vertex v with f(v) > 0. The problem is solvable in polynomial time on a general graph (Heggernes and Lokshtanov, Disc Math (2006), 3267-3280) and Blair et al. (Congr. Num. (2004), 55-77.) gave an O(n(2)) algorithm for trees. In this article, we provide an O(n) algorithm for trees. Our algorithm is notable due to the fact that it makes decisions for each vertex v based on "nonlocal" information from vertices far away from v, whereas almost all other linear-time algorithms for trees only make use of local information. (C) 2008 Wiley Periodicals, Inc. NETWORKS, Vol. 53(2), 160-169 2009

关键词： broadcasts domination tree algorithms linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

The 2-terminal-set path cover problem and its polynomial solution on cographs

The 2-terminal-set path cover problem and its polynomial sol...

引用

2nd Annual International Workshop on Frontiers in Algorithmics

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

ISBN: (纸本)9783540693109

In this paper we study a generalization of the path cover problem, namely, the 2-terminal-set path cover problem, or 2TPC for short. Given a graph G and two disjoint subsets T-1 and T-2 of V(G), a 2-terminal-set path cover of G with respect to T-1 and T-2 is a set of vertex-disjoint paths P that covers the vertices of G such that the vertices of T-1 and T-2 are all endpoints of the paths in P and all the paths with 2 both endpoints in T-1 boolean OR T-2 have one endpoint in T-1 and the other in T-2. The 2TPC problem is to find a 2-terminal-set path cover of G of minimum cardinality;note that, if T-1 boolean OR T-2 is empty, the stated problem coincides with the classical path cover problem. The 2TPC problem generalizes some path cover related problems, such as the 1HP and 2HP problems, which have been proved to be NP-complete even for small classes of graphs. We show that the 2TPC problem can be solved in linear time on the class of cographs. The proposed linear-time algorithm is simple, requires linear space, and also enables us to solve the 1HP and 2HP problems on cographs within the same time and space complexity.

关键词： path cover fixed-endpoint path cover perfect graphs complement reducible graphs cographs 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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：