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

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

来源：评论

学校读者我要写书评

暂无评论

Minimal separators in extended P₄-laden graphs

引用

DISCRETE APPLIED MATHEMATICS 2012年第18期160卷 2769-2777页

作者： Pedrotti, Vagner de Mello, Celia Picinin Univ Estadual Campinas Inst Comp Campinas SP Brazil Univ Fed Mato Grosso do Sul Fac Comp Campo Grande Brazil

In this paper, we use the primeval decomposition tree to compute the minimal separators of some graphs and to describe a linear-time algorithm that lists the minimal separators of extended P-4-laden graphs, extending an algorithm for P-4-sparse graphs given by Nikolopoulos and Palios [S.D. Nikolopoulos, L Palios, Minimal separators in P-4-sparse graphs, Discrete Math. 306 (3) (2006) 381-392]. We also give bounds on the number and total size of all minimal separators of extended P-4-laden graphs and some of their subclasses, such as P-4-tidy and P-4-lite graphs. Moreover, we show that these bounds are tight for all subclasses considered. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Minimal separators Primeval decomposition Modular decomposition Graphs with few P-4's linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

On cherry-picking and network containment

引用

THEORETICAL COMPUTER SCIENCE 2021年 856卷 121-150页

作者： Janssen, Remie Murakami, Yukihiro Delft Univ Technol Delft Inst Appl Math Van Mourik Broekmanweg 6 NL-2628 XE Delft Netherlands

Phylogenetic networks are used to represent evolutionary scenarios in biology and linguistics. To find the most probable scenario, it may be necessary to compare candidate networks. In particular, one needs to distinguish different networks and determine whether one network is contained in another. In this paper, we introduce cherry-picking networks, a class of networks that can be reduced by a so-called cherry-picking sequence. We then show how to compare such networks using their sequences. We characterize reconstructible cherry-picking networks, which are the networks that are uniquely determined by the sequences that reduce them, making them distinguishable. Furthermore, we show that a cherry-picking network is contained in another cherry picking network if a sequence for the latter network reduces the former network, provided both networks can be reconstructed from their sequences in a similar way (i.e., they are in the same reconstructible class). Lastly, we show that the converse of the above statement holds for tree-child networks, thereby showing that NETWORK CONTAINMENT, the problem of checking whether a network is contained in another, can be solved by computing cherry picking sequences in linear time for tree-child networks. (C) 2020 The Author(s). Published by Elsevier B.V.

关键词： Phylogenetic networks Network containment Cherry-picking sequences Tree containment linear-time algorithms Cherry-picking networks

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

On-line construction of compact directed acyclic word graphs

引用

DISCRETE APPLIED MATHEMATICS 2005年第2期146卷 156-179页

作者： Inenaga, S Hoshino, H Shinohara, A Takeda, M Arikawa, S Mauri, G Pavesi, G Kyushu Univ Dept Informat Fukuoka 812 Japan Univ Milan Biccoca Dept Comp Sci Syst & Commun Milan Italy

Many different index structures, providing efficient solutions to problems related to pattern matching, have been introduced so far. Examples of these structures are suffix trees and directed acyclic word graphs (DAWGs), which can be efficiently constructed in linear time and space. Compact directed acyclic word graphs (CDAWGs) are an index structure preserving some features of both suffix trees and DAWGs, and require less space than both of them. An algorithm which directly constructs CDAWGs in linear time and space was first introduced by Crochemore and Verin, based on McCreight's algorithm for constructing suffix trees. In this work, we present a novel on-line linear-time algorithm that builds the CDAWG for a single string as well as for a set of strings, inspired by Ukkonen's on-line algorithm for constructing suffix trees. (C) 2004 Elsevier B.V. All rights reserved.

关键词： pattern matching on strings compact directed acyclic word graphs directed acyclic word graphs suffix trees on-line and linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Online Matroid Intersection: Beating Half for Random Arrival 19th

Online Matroid Intersection: Beating Half for Random Arrival

引用

19th International Conference on Integer Programming and Combinatorial Optimization (IPCO)

作者： Guruganesh, Guru Prashanth Singla, Sahil Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA

ISBN: (纸本)9783319592503;9783319592497

For two matroids M-1 and M-2 defined on the same ground set E, the online matroid intersection problem is to design an algorithm that constructs a large common independent set in an online fashion. The algorithm is presented with the ground set elements one-by-one in a uniformly random order. At each step, the algorithm must irrevocably decide whether to pick the element, while always maintaining a common independent set. While the natural greedy algorithm-pick an element whenever possible-is half competitive, nothing better was previously known;even for the special case of online bipartite matching in the edge arrival model. We present the first randomized online algorithm that has a 1/2 + delta competitive ratio in expectation, where delta > 0 is a constant. The expectation is over the random order and the coin tosses of the algorithm. As a corollary, we also obtain the first linear time algorithm that beats half competitiveness for offline matroid intersection.

关键词： Online algorithms Matroid intersection Randomized algorithms Competitive analysis linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Structured Watermarks for Structured Software

引用

SN Computer Science 2024年第5期5卷 568页

作者： Bento, Lucila M. S. Boccardo, Davidson R. Machado, Raphael C. S. Pereira de Sá, Vinícius G. Szwarcfiter, Jayme L. State University of Rio de Janeiro São Francisco Xavier St. RJ Rio de Janeiro 20550-000 Brazil Federal University of Rio de Janeiro Athos da Silveira Ramos Ave RJ Rio de Janeiro 21941-916 Brazil Fluminense Federal University Gal. Milton Tavares de Souza Ave RJ Niterói 24210-310 Brazil Albert Einstein Israelite Hospital Brigadeiro Faria Lima Ave SP São Paulo 01451-001 Brazil

Software watermarking involves integrating an identifier within the software, enabling timely retrieval to disclose authorship/ownership, and deter piracy. Various software watermarking schemes have been proposed in the literature, many of which involve statically embedding an encoded identifier into the control flow graph of the program. In this paper, we propose novel embedding and extraction algorithms characterized by four key features: randomization, generating watermarks with a size closely matching the number of bits in the identifier, implementing both encoding and decoding with linear time complexity, and, most importantly, generating watermarks that conform to structured code. We emphasize the capability to encode the same identifier as distinct graphs, coupled with the absence of cumbersome “GOTO”-like substructures, as enhancements to the stealthiness of our watermarks. This feature makes them more resilient to common forms of attack, contributing to their effectiveness in safeguarding software integrity and discouraging unauthorized use. © The Author(s), under exclusive licence to Springer Nature Singapore Pte Ltd. 2024.

关键词： linear-time algorithms Software watermarking Structured code

来源：评论

学校读者我要写书评

暂无评论

On-line construction of compact directed acyclic word graphs 1

引用

12th Annual Symposium on Combinatorial Pattern Matching (CPM 2001)

作者： Inenaga, S Hoshino, H Shinohara, A Takeda, M Arikawa, S Mauri, G Pavesi, G Kyushu Univ Dept Informat Fukuoka 812 Japan Univ Milan Biccoca Dept Comp Sci Syst & Commun Milan Italy

ISBN: (数字)9783540481942

ISBN: (纸本)9783540422716

关键词： pattern matching on strings compact directed acyclic word graphs directed acyclic word graphs suffix trees on-line and 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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：