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

Hardness and inapproximability of convex recoloring problems

THEORETICAL COMPUTER SCIENCE 2014年 533卷 15-25页

作者： Campelo, Manoel Huiban, Cristiana Sampaio, Rudini M. Wakabayashi, Yoshiko Univ Fed Ceara Dept Estat & Matemat Aplicada Fortaleza Ceara Brazil Univ Fed Pernambuco Ctr Informat Recife PE Brazil Univ Fed Ceara Dept Comp Fortaleza Ceara Brazil Univ Sao Paulo Inst Matemat & Estat Sao Paulo Brazil

Given a graph with an arbitrary vertex coloring, the Convex Recoloring Problem (CR) consists in recoloring the minimum number of vertices so that each color induces a connected subgraph. We focus on the complexity and inapproximability of this problem on k-colored graphs, for fixed k 2. We prove a strong complexity result showing that, for each k 2, CR is already NP-hard on k-colored grids, and therefore also on planar graphs with maximum degree 4. For each k 2, we prove that, for a positive constant c, there is no c Inn-approximation algorithm for k-colored n-vertex (bipartite) graphs, unless P = NP. We also prove that CR parameterized by the number of color changes is W[2]-hard. For 2-colored (q, q 4)-graphs, a class that includes cographs and P4-sparse graphs, we present linear-time algorithms for fixed q. The same complexity and inapproximability results are obtained for two relaxations of the problem, where only one fixed color or any color is required to induce a connected subgraph, respectively. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Convex recoloring Complexity Inapproximability linear-time algorithm Grid graph (q, q-4)-graph

来源：评论

学校读者我要写书评

暂无评论

MINIMIZING EXTERNAL WIRES IN GENERALIZED SINGLE-ROW ROUTING

引用

IEEE TRANSACTIONS ON COMPUTERS 1992年第6期41卷 771-776页

作者： BLAIR, JRS LLOYD, EL UNIV DELAWARE DEPT COMP SCINEWARKDE 19716

Much of the recent work on the automated design of VLSI chips has concentrated on routing problems associated with such designs. One major class of routing problems focuses on single-row routing. Recently, the traditional single-row routing model has been generalized to allow external wires. Under this generalized model, it is possible to route many more single-row routing instances than in the traditional model. There is, however, a clear disadvantage in the use of external wires. since they force a lengthening of the channels surrounding the single row of terminals. Thus, it is desirable for these generalized single-row routings to use a minimum number of external wires. In this note, we provide a linear-time algorithm for determining the minimum number of external wires needed to route a given instance of single-row routing.

关键词： GENERALIZED SINGLE-ROW ROUTING linear-time algorithm MINIMIZATION OF EXTERNAL WIRES SINGLE LAYER VLSI DESIGN

来源：评论

学校读者我要写书评

暂无评论

Testing bandwidth k for k-connected graphs

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2003年第2期16卷 301-312页

作者： Engel, K Guttmann, S Univ Rostock Fachbereich Math D-18051 Rostock Germany Arvato Syst GmbH D-33311 Gutersloh Germany

We present a linear-time algorithm to decide whether a given k-connected graph has bandwidth k, where k is a fixed positive integer. This improves the general O(n(k))-time-algorithm of Gurari and Sudborough, based on a dynamic programming approach of Saxe, for the recognition of bandwidth-k graphs on n vertices in the special case of connectivity k.

关键词： bandwidth bandwidth-k graph k-connected graph linear-time algorithm linear layout start sequence

来源：评论

学校读者我要写书评

暂无评论

ONLINE CONSTRUCTION OF SUFFIX TREES

引用

algorithmICA 1995年第3期14卷 249-260页

作者： UKKONEN, E Department of Computer Science University of Helsinki Teollisuuskatu 23

An on-line algorithm is presented for constructing the suffix tree for a given string in time linear in the length of the string. The new algorithm has the desirable property of processing the string symbol by symbol from left to right. It always has the suffix tree for the scanned part of the string ready. The method is developed as a linear-time version of a very simple algorithm for (quadratic size) suffix tries. Regardless of its quadratic worst case this latter algorithm can be a good practical method when the string is not too long. Another variation of this method is shown to give, ina natural way, the well-known algorithms for constructing suffix automata (DAWGs).

关键词： linear-time algorithm SUFFIX TREE SUFFIX TRIE SUFFIX AUTOMATON DAWG

来源：评论

学校读者我要写书评

暂无评论

Dividing Splittable Goods Evenly and With Limited Fragmentation

引用

algorithmICA 2020年第5期82卷 1298-1328页

作者： Damaschke, Peter Chalmers Univ Dept Comp Sci & Engn S-41296 Gothenburg Sweden

A splittable good provided in n pieces shall be divided as evenly as possible among m agents, where every agent can take shares from at most F pieces. We call F the fragmentation and mainly restrict attention to the cases F = 1 and F = 2. For F = 1, the max-min and min-max problems are solvable in linear time. The case F = 2 has neat formulations and structural characterizations in terms of weighted graphs. First we focus on perfectly balanced solutions. While the problem is strongly NP-hard in general, it can be solved in linear time if m = n - 1, and a solution always exists in this case, in contrast to F = 1. Moreover, the problem is fixed-parameter tractable in the parameter 2m - n. (Note that this parameter measures the number of agents above the trivial threshold m = n/2.) The structural results suggest another related problem where unsplittable items shall be assigned to subsets so as to balance the average sizes (rather than the total sizes) in these subsets. We give an approximationpreserving reduction from our original splitting problem with fragmentation F = 2 to this averaging problem, and some approximation results in cases when m is close to either n or n/2.

关键词： Fair division Weighted graph linear-time algorithm Parameterized algorithm Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

ORIENTATION OF FITCH GRAPHS AND RECONCILIATION-FREE INFERENCE OF HORIZONTAL GENE TRANSFER IN GENE TREES

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2023年第3期37卷 2172-2207页

作者： Schaller, David Hellmuth, Marc Stadler, Peter F. Univ Leipzig Dept Comp Sci Bioinformat Grp D-04107 Leipzig Germany Univ Leipzig Interdisciplinary Ctr Bioinformat D-04107 Leipzig Germany Stockholm Univ Dept Math Fac Sci SE-10691 Stockholm Sweden Univ Leipzig German Ctr Integrat Biodivers Res iDiv Halle Jena Competence Ctr Scalable Data Serv & Solut Dresden Leipzig Res Ctr Civilizat Dis D-04103 Leipzig Germany Univ Leipzig Univ Leipzig Ctr Biotechnol & Biomed Max Planck Inst Math Sci D-04103 Leipzig Germany Univ Vienna Inst Theoret Chem A-1090 Vienna Austria Univ Nacl Colombia Fac Ciencias Bogota Colombia Santa Fe Inst Santa Fe NM 87501 USA

Horizontal gene transfer (HGT) events partition a gene tree T, and thus its leaf set X, into subsets of genes whose evolutionary history is described by speciation and duplication events alone. Two genes thus are xenologs if and only if they belong to two different sets of this partition P. Indirect phylogenetic methods can be used to infer the partition P of X from sequence similarity or evolutionary distances without any a priori knowledge about the underlying tree T. In this contribution, we assume that a partition P of the gene set X and a usually incompletely resolved estimate T of the original gene tree on X are known. We then ask to what extent T and P can be combined to determine the horizontal transfer edges in T and thus the orientation of the HGT events that separate the sets of P. If T and P are compatible, it can be decided for each pair of genes x and y whether there always exists or never exists a horizontal gene transfer in T along the path connecting y and the most recent common ancestor of x and y, and thus a directed edge (x, y) in the so-called Fitch graph of the gene family. We generalize this result to insufficiently resolved gene trees. We show that the classification of a gene pair (x, y) can be computed in constant time after linear-time preprocessing. Using simulated gene family histories, we observe empirically that the vast majority of horizontal transfer edges in the gene tree T can be recovered unambiguously from the knowledge of the partition P. All algorithms developed here are implemented and freely available within the Python package AsymmeTree hosted at https://***/david-schaller/AsymmeTree.

关键词： gene families xenology horizontal gene transfer Fitch graph partition linear-time algorithm

来源：评论

学校读者我要写书评

暂无评论

On total f-domination: Polyhedral and algorithmic results

引用

DISCRETE APPLIED MATHEMATICS 2019年 258卷 97-104页

作者： Dell'Amico, Mauro Neto, Jose Univ Modena & Reggio Emilia Dept Sci & Methods Engn Via Amendola 2 I-42122 Reggio Emilia Italy Univ Paris Saclay CNRS Telecom SudParis Samovar 9 Rue Charles Fourier F-91011 Evry France

Given a graph G = (V, E) and integer values f(v), v is an element of V, a node subset D subset of V is a total f -dominating set if every node v is an element of V is adjacent to at least f(v) nodes of D. Given a weight system c(v), v is an element of V, the minimum weight total f-dominating set problem is to find a total f-dominating set of minimum total weight. In this article, we propose a polyhedral study of the associated polytope together with a complete and compact description of the polytope for totally unimodular graphs and cycles. We also propose a linear time dynamic programming algorithm for the case of trees. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Total domination Polytope Tree linear-time algorithm

来源：评论

学校读者我要写书评

暂无评论

The obnoxious center problem on a tree

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2001年第4期14卷 498-509页

作者： Burkard, RE Dollani, H Lin, YX Rote, G Graz Tech Univ Inst Math A-8010 Graz Austria Zhengzhou Univ Dept Math Zhengzhou 450052 Peoples R China Free Univ Berlin Inst Informat D-14195 Berlin Germany

The obnoxious center problem in a graph G asks for a location on an edge of the graph such that the minimum weighted distance from this point to a vertex of the graph is as large as possible. We derive algorithms with linear running time for the cases when G is a path or a star, thus improving previous results of Tamir [SIAM J. Discrete Math, 1 (1988), pp. 377-396]. For subdivided stars we present an algorithm of running time O (n log n). For general trees, we improve an algorithm of Tamir [SIAM J. Discrete Math, 1 (1988), pp. 377-396] by a factor of log n. Moreover, a linear algorithm for the unweighted center problem on an arbitrary tree with neutral and obnoxious vertices is described.

关键词： location problems center problem obnoxious facilities linear-time algorithm

来源：评论

学校读者我要写书评

暂无评论

ONE-SIDE NIELSEN TRANSFORMATIONS IN FREE GROUPS

引用

INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION 2009年第7期19卷 855-871页

作者： Vernitski, Alexei Univ Essex Dept Math Sci Colchester CO4 3SQ Essex England

We study a graph related to the Andrews-Curtis graph. The vertices are pairs of elements of a free group, and two vertices are adjacent if they can be obtained from one another by a left Nielsen transformation, that is, for each two words u, v the pair (u, v) is adjacent to (vu, v), (v(-1)u, v), (u, uv), and (u, u(-1)v). We study connected components of the graph and describe the shortest pairs in all components. Hence, we find a linear-time algorithm for checking whether two pairs belong to the same connected component of the graph.

关键词： Free group Nielsen transformation Andrews-Curtis graph connected component linear-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Remarks on Privileged Words

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2016年第4期27卷 431-442页

作者： Forsyth, Michael Jayakumar, Amlesh Peltomaki, Jarkko Shallit, Jeffrey Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada Turku Ctr Comp Sci TUCS Turku 20520 Finland Univ Turku Dept Math & Stat Turku 20014 Finland

We discuss the notion of privileged word, recently introduced by Kellendonk, Lenz and Savinien. A word w is privileged if it is of length = 1, then w(j) is privileged for all j >= 0;(2) the language of privileged w... 详细信息

We discuss the notion of privileged word, recently introduced by Kellendonk, Lenz and Savinien. A word w is privileged if it is of length <= 1, or has a privileged border that occurs exactly twice in w. We prove the following results: (1) if w(k) is privileged for some k >= 1, then w(j) is privileged for all j >= 0;(2) the language of privileged words is not context-free;(3) there is a linear-time algorithm to check if a given word is privileged;and (4) there are at least 2(n-4)/n(2) privileged binary words of length n

关键词： Privileged word regular language linear-time algorithm context-free language enumeration

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：