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

Orienting undirected phylogenetic networks

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2024年 140卷

作者： Huber, Katharina T. van Iersel, Leo Janssen, Remie Jones, Mark Moulton, Vincent Murakami, Yukihiro Semple, Charles Univ East Anglia Sch Comp Sci Norwich NR4 7TJ England Delft Univ Technol Delft Inst Appl Math Van Mourik Broekmanweg 6 NL-2628 XE Delft Netherlands Univ Canterbury Sch Math & Stat Private Bag 4800 Christchurch 8140 New Zealand

This paper studies the relationship between undirected (unrooted) and directed (rooted) phylogenetic networks. We describe a polynomial-time algorithm for deciding whether an undirected nonbinary phylogenetic network, given the locations of the root and reticulation vertices, can be oriented as a directed nonbinary phylogenetic network. Moreover, we characterize when this is possible and show that, in such instances, the resulting directed nonbinary phylogenetic network is unique. In addition, without being given the location of the root and the reticulation vertices, we describe an algorithm for deciding whether an undirected binary phylogenetic network N can be oriented as a directed binary phylogenetic network of a certain class. The algorithm is fixed-parameter tractable (FPT) when the parameter is the level of N and is applicable to classes of directed phylogenetic networks that satisfy certain conditions. As an example, we show that the well-studied class of binary tree-child networks satisfies these conditions.(c) 2023 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： Phylogenetic network Graph orientation Graph algorithm Fixed-parameter tractability polynomial-time algorithm Characterization Computational biology Phylogenetics

来源：评论

学校读者我要写书评

暂无评论

AUTOMATIC RECOGNITION OF TRACTABILITY IN INFERENCE RELATIONS

引用

JOURNAL OF THE ACM 1993年第2期40卷 284-303页

作者： MCALLESTER, DA Massachusetts Institute of Technology Cambridge MA

A procedure is given for recognizing sets of inference rules that generate polynomial time decidable inference relations. The procedure can automatically recognize the tractability of the inference rules underlying congruence closure. The recognition of tractability for that particular rule set constitutes mechanical verification of a theorem originally proved independently by Kozen and Shostak. The procedure is algorithmic, rather than heuristic, and the class of automatically recognizable tractable rule sets can be precisely characterized. A series of examples of rule sets whose tractability is nontrivial, yet machine recognizable, is also given. The technical framework developed here is viewed as a first step toward a general theory of tractable inference relations.

关键词： algorithmS DEDUCTION AUTOMATED REASONING INFERENCE RULES MACHINE INFERENCE MECHANICAL VERIFICATION polynomial-time algorithm PROOF SYSTEMS PROOF THEORY THEOREM PROVING

来源：评论

学校读者我要写书评

暂无评论

Min-Max Scheduling of Batch or Drop-Line Jobs Under Agreeable Release and Processing times

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2022年第2期39卷 2150023-2150023页

作者： Gao, Yuan Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China Zhengzhou Univ Sch Informat Engn Zhengzhou 450001 Henan Peoples R China

We study the Pareto optimization scheduling on an unbounded parallel-batch machine with jobs having agreeable release dates and processing times for minimizing makespan and maximum cost simultaneously. The jobs considered in this paper are of two types: batch jobs and drop-line jobs. For batch jobs, the completion time of a job is given by the completion time of the batch containing this job. For drop-line jobs, the completion time of a job is given by the starting time of the batch containing this job plus the processing time of this job. For both of batch jobs and drop-line jobs, we present polynomial-time algorithms for finding all Pareto optimal points.

关键词： Parallel-batch scheduling release dates pareto optimization polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Polymatching algorithm in observational studies with multiple treatment groups

引用

COMPUTATIONAL STATISTICS & DATA ANALYSIS 2022年 167卷 107364-107364页

作者： Nattino, Giovanni Song, Chi Lu, Bo Ist Ric Farmacol Mario Negri IRCCS Via GB Camozzi 3 I-24020 Ranica BG Italy Ohio State Univ Div Biostat Coll Publ Hlth 1841 Neil Ave Columbus OH 43210 USA

Matched designs are commonly used in non-randomized studies to evaluate causal effects for dichotomous treatment. Optimal matching algorithms have been devised to form matched pairs or sets between treatment and control groups in various designs, including 1-k matching and full matching. With multiple treatment arms, however, the optimal matching problem cannot be solved in polynomial-time. This is a major challenge for implementing matched designs with multiple arms, which are important for evaluating causal effects with different dose levels or constructing evidence factors with multiple control groups. A polymatching framework for generating matched sets among multiple groups is proposed. An iterative multi-way algorithm for implementation is developed, which takes advantage of the existing optimal two-group matching algorithm repeatedly. An upper bound for the total distance attained by our algorithm is provided to show that the distance result is close to the optimal solution. Simulation studies are conducted to compare the proposed algorithm with the nearest neighbor algorithm under different scenarios. The algorithm is also used to construct a difference-in-difference matched design among four groups, to examine the impact of Medicaid expansion on the health status of Ohioans. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Polymatching Multiple treatment groups polynomial-time algorithm Causal inference Difference-in-difference

来源：评论

学校读者我要写书评

暂无评论

An algorithm for reconstructing level-2 phylogenetic networks from trinets

引用

INFORMATION PROCESSING LETTERS 2022年 178卷

作者： van Iersel, Leo Kole, Sjors Moulton, Vincent Nipius, Leonie Delft Univ Technol Delft Inst Appl Math Mekelweg 4 NL-2628CD Delft Netherlands Univ East Anglia Sch Comp Sci Norwich NR4 7TJ Norfolk England

Evolutionary histories for species that cross with one another or exchange genetic material can be represented by leaf-labelled, directed graphs called phylogenetic networks. A major challenge in the burgeoning area of phylogenetic networks is to develop algorithms for building such networks by amalgamating small networks into a single large network. The level of a phylogenetic network is a measure of its deviation from being a tree;the higher the level of a network, the less treelike it becomes. Various algorithms have been developed for building level-1 networks from small networks. However, level-1 networks may not be able to capture the complexity of some data sets. In this paper, we present a polynomial-time algorithm for constructing a rooted binary level-2 phylogenetic network from a collection of 3-leaf networks or trinets. Moreover, we prove that the algorithm will correctly reconstruct such a network if it is given all of the trinets in the network as input. The algorithm runs in time O (t middot n + n4) with t the number of input trinets and n the number of leaves. We also show that there is a fundamental obstruction to constructing level-3 networks from trinets, and so new approaches will need to be developed for constructing level-3 and higher level-networks.(c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Directed graph Phylogenetic network polynomial-time algorithm Subnetworks Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Defective incidence coloring of graphs

引用

APPLIED MATHEMATICS AND COMPUTATION 2023年第1期443卷

作者： Bi, Huimin Zhang, Xin Xidian Univ Sch Math & Stat Xian 710071 Peoples R China

We define the d-defective incidence chromatic number of a graph, generalizing the notion of incidence chromatic number, and determine it for some classes of graphs including trees, complete bipartite graphs, complete graphs, and outerplanar graphs. Fast algorithms for constructing the optimal d-defective incidence colorings of those graphs are presented. (c) 2022 Elsevier Inc. All rights reserved.

关键词： Incidence coloring Defective coloring Latin square Outerplanar graph polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Interference-free walks in time: temporally disjoint paths

引用

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2023年第1期37卷 1-1页

作者： Klobas, Nina Mertzios, George B. Molter, Hendrik Niedermeier, Rolf Zschoche, Philipp Univ Durham Dept Comp Sci Upper Mountjoy CampusStockton Rd Durham DH1 3LE England Ben Gurion Univ Negev Dept Ind Engn & Management David Ben Gurion Blvd IL-84105 Beer Sheva Israel TU Berlin Fac 4 Algorithm & Computat Complex Ernst Reuter Pl 7 D-10587 Berlin Germany

We investigate the computational complexity of finding temporally disjoint paths and walks in temporal graphs. There, the edge set changes over discrete time steps. Temporal paths and walks use edges that appear at monotonically increasing time steps. Two paths (or walks) are temporally disjoint if they never visit the same vertex at the same time;otherwise, they interfere. This reflects applications in robotics, traffic routing, or finding safe pathways in dynamically changing networks. At one extreme, we show that on general graphs the problem is computationally hard. The path version is NP-hard even if we want to find only two temporally disjoint paths. The walk version is W-hard (Klobas in IJCAI 4090-4096, 2021) when parameterized by the number of walks. However, it is polynomial-time solvable for any constant number of walks. At the other extreme, restricting the input temporal graph to have a path as underlying graph, quite counter-intuitively, we find NP-hardness in general but also identify natural tractable cases.

关键词： Temporal graph Temporal path NP-complete problem Parameterized complexity polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

The Complexity of the

引用

SIAM Journal on Computing 2000年第6期29卷 1878-1888页

作者： Jin-yi Cai Richard J. Lipton Yechezkel Zalcstein

We present a deterministic polynomial-time algorithm for the A B C problem, which is the membership problem for 2-generated commutative linear semigroups over an algebraic number field. We also obtain a polynomial-tim... 详细信息

We present a deterministic polynomial-time algorithm for the A B C problem, which is the membership problem for 2-generated commutative linear semigroups over an algebraic number field. We also obtain a polynomial-time algorithm for the (easier) membership problem for 2-generated abelian linear groups. Furthermore, we provide a polynomial-sized encoding for the set of all solutions.

关键词： 20M99 68Q25 68W40 polynomial-time algorithm membership problem semigroup commutative lattice

来源：评论

学校读者我要写书评

暂无评论

Single Track Transportation in a Two-Machine Production System

引用

IFAC-PapersOnLine 2022年第10期55卷 2893-2897页

作者： Yakov Zinder Alexander Lazarev Elena Musatova University of Technology Sydney Australia V.A. Trapeznikov Institute of Control Science of Russian Academy of Sciences Moscow Russia

The paper is concerned with scheduling traffic on a single track between two stations which generate requests for transportation with different release times. These requests are served by a fleet of identical vehicles, each of which can serve (carry) several requests for transportation simultaneously. The single track, used by the vehicles, does not permit traffic in both directions simultaneously. The presented polynomial-time algorithms are based on dynamic programming.

关键词： Scheduling dynamic programming single track polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

On Some Efficiently Solvable Classes of the Network Facility Location Problem with Constraints on the Capacities of Communication Lines

引用

PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS 2021年第SUPPL 1期313卷 S58-S72页

作者： Gimadi, E. Kh. Tsidulko, O. Yu. Russian Acad Sci Sobolev Inst Math Siberian Branch Novosibirsk 630090 Russia Novosibirsk State Univ Novosibirsk 630090 Russia

We study the network facility location problem with constraints on the capacities of communication lines, called Restricted Facility Location Problem (RFLP). It is required to locate facilities at the vertices of a given network graph so as to simultaneously satisfy at minimum cost the demands of customers located at the vertices of the graph. We consider two statements of the problem: the multiple allocation RFLP, where the demand of a customer can be satisfied jointly by several facilities, and the single allocation RFLP, where the demand of a customer must be entirely satisfied by a single facility. We show that the single allocation RFLP is NP-hard even if the network is a simple path and strongly NP-hard if the network is a tree. The multiple allocation RFLP is weakly NP-hard on trees. For this problem, we propose a pseudopolynomial-time algorithm for the case where the network graph has constant treewidth and a linear-time algorithm for the case where the network is a simple path.

关键词： facility location problem capacities multiple allocation single allocation NP-hard problem treewidth pseudopolynomial-time algorithm polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：