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

Maximizing the Average Environmental Benefit of a Fleet of Drones under a Periodic Schedule of Tasks

algorithmS 2024年第7期17卷 283页

作者： Kats, Vladimir Levner, Eugene Ben Gurion Univ Negev Inst Ind Math IL-8424902 Beer Sheva Israel Holon Inst Technol Sch Comp Sci IL-5810201 Holon Israel

Unmanned aerial vehicles (UAVs, drones) are not just a technological achievement based on modern ideas of artificial intelligence;they also provide a sustainable solution for green technologies in logistics, transport, and material handling. In particular, using battery-powered UAVs to transport products can significantly decrease energy and fuel expenses, reduce environmental pollution, and improve the efficiency of clean technologies through improved energy-saving efficiency. We consider the problem of maximizing the average environmental benefit of a fleet of drones given a periodic schedule of tasks performed by the fleet of vehicles. To solve the problem efficiently, we formulate it as an optimization problem on an infinite periodic graph and reduce it to a special type of parametric assignment problem. We exactly solve the problem under consideration in O(n3) time, where n is the number of flights performed by UAVs.

关键词： sustainable scheduling fleet of drones maximizing the environmental benefit polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

On the maximum independent set problem in subclasses of subcubic graphs

引用

JOURNAL OF DISCRETE algorithmS 2015年 31卷 104-112页

作者： Lozin, Vadim Monnot, Jerome Ries, Bernard Univ Warwick DIMAP Coventry CV4 7AL W Midlands England Univ Warwick Math Inst Coventry CV4 7AL W Midlands England CNRS LAMSADE UMR 7243 F-75700 Paris France Univ Paris 09 PSL F-75775 Paris 16 France

It is known that the maximum independent set problem is NP-complete for subcubic graphs, i.e. graphs of vertex degree at most 3. Moreover, the problem is NP-complete for 3-regular Hamiltonian graphs and for H-free subcubic graphs whenever H contains a connected component which is not a tree with at most 3 leaves. We show that if every connected component of His a tree with at most 3 leaves and at most 7 vertices, then the problem can be solved for H-free subcubic graphs in polynomial time. We also strengthen the NP-completeness of the problem on 3-regular Hamiltonian graphs by showing that the problem is APX-complete in this class. (c) 2014 Elsevier B.V. All rights reserved.

关键词： Independent set polynomial-time algorithm Subcubic graph APX-completeness

来源：评论

学校读者我要写书评

暂无评论

Reconstruction of time-consistent species trees

引用

algorithmS FOR MOLECULAR BIOLOGY 2020年第1期15卷 16-16页

作者： Lafond, Manuel Hellmuth, Marc Univ Sherbrooke Dept Comp Sci 2500 Boul Univ Sherbrooke PQ J1K 2R1 Canada Univ Leeds Sch Comp EC Stoner Bldg Leeds LS2 9JT W Yorkshire England

Background The history of gene families-which are equivalent to event-labeled gene trees-can to some extent be reconstructed from empirically estimated evolutionary event-relations containing pairs of orthologous, paralogous or xenologous genes. The question then arises as whether inferred event-labeled gene trees are "biologically feasible" which is the case if one can find a species tree with which the gene tree can be reconciled in a time-consistent way. Results In this contribution, we consider event-labeled gene trees that contain speciations, duplications as well as horizontal gene transfer (HGT) and we assume that the species tree is unknown. Although many problems become NP-hard as soon as HGT and time-consistency are involved, we show, in contrast, that the problem of finding a time-consistent species tree for a given event-labeled gene can be solved in polynomial-time. We provide a cubic-time algorithm to decide whether a "time-consistent" species tree for a given event-labeled gene tree exists and, in the affirmative case, to construct the species tree within the same time-complexity.

关键词： Tree reconciliation Gene evolution Species evolution Horizontal gene transfer time-consistency polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A MATHEMATICAL COMMITMENT WITHOUT COMPUTATIONAL STRENGTH

引用

REVIEW OF SYMBOLIC LOGIC 2022年第4期15卷 880-906页

作者： Freund, Anton Tech Univ Darmstadt Fachbereich Math Schlossgartenstr 7 D-64289 Darmstadt Germany

We present a new manifestation of Godel's second incompleteness theorem and discuss its foundational significance, in particular with respect to Hilbert's program. Specifically, we consider a proper extension of Peano arithmetic (PA) by a mathematically meaningful axiom scheme that consists of Sigma(0)(2)-sentences. These sentences assert that each computably enumerable Sigma(0)(2)-definable without parameters) property of finite binary trees has a finite basis. Since this fact entails the existence of polynomial time algorithms, it is relevant for computer science. On a technical level, our axiom scheme is a variant of an independence result due to Harvey Friedman. At the same time, the meta-mathematical properties of our axiom scheme distinguish it from most known independence results: Due to its logical complexity, our axiom scheme does not add computational strength. The only known method to establish its independence relies on Godel's second incompleteness theorem. In contrast, Godel's theorem is not needed for typical examples of Pi(0)(2)-independence (such as the Paris-Harrington principle), since computational strength provides an extensional invariant on the level of Pi(0)(2)-sentences.

关键词： independence computational strength Godel's second incompleteness theorem Hilbert's program Kruskal's theorem polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A network flow approach to a common generalization of Clar and Fries numbers

引用

DISCRETE MATHEMATICS 2024年第11期347卷

作者： Berczi-Kovacs, Erika Frank, Andras HUN REN Alfred Renyi Inst Math Budapest Hungary HUN REN ELTE Egervary Res Grp Combinatorial Optimi Budapest Hungary Eotvos Lorand Univ Dept Operat Res Budapest Hungary

Clar number and Fries number are two thoroughly investigated parameters of plane graphs emerging from mathematical chemistry to measure stability of organic molecules. First, we introduce a common generalization of these two concepts for bipartite plane graphs, and then we extend it further to the notion of source-sink pairs of subsets of nodes in a general (not necessarily planar) directed graph. The main result is a min-max formula for the maximum weight of a source-sink pair. The proof is based on the recognition that the convex hull of source-sink pairs can be obtained as the projection of a network tension polyhedron. The construction makes it possible to apply any standard cheapest network flow algorithm to compute both a maximum weight source-sink pair and a minimizer of the dual optimization problem formulated in the min-max theorem. As a consequence, our approach gives rise to the first purely combinatorial, strongly polynomial algorithm to compute a largest (or even a maximum weight) Fries-set of a perfectly matchable plane bipartite graph and an optimal solution to the dual minimization problem. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： Clar number Fries number polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Arc-Completion of 2-Colored Best Match Graphs to Binary-Explainable Best Match Graphs

引用

algorithmS 2021年第4期14卷 110页

作者： Schaller, David Geiss, Manuela Hellmuth, Marc Stadler, Peter F. Max Planck Inst Math Sci D-04103 Leipzig Germany Univ Leipzig Bioinformat Grp Dept Comp Sci D-04107 Leipzig Germany Univ Leipzig Interdisciplinary Ctr Bioinformat D-04107 Leipzig Germany Software Competence Ctr Hagenberg GmbH SCCH A-4232 Hagenberg Austria Stockholm Univ Fac Sci Dept Math SE-10691 Stockholm Sweden Univ Leipzig Competence Ctr Scalable Data Serv & Solut Leipzig Res Ctr Civilizat Dis Res iDiv Halle Jena LeipzigGerman Ctr Integrat B D-04103 Leipzig Germany Univ Leipzig Leipzig Res Ctr Civilizat Dis LIFE D-04103 Leipzig Germany Univ Vienna Inst Theoret Chem A-1090 Vienna Austria Univ Nacl Colombia Fac Ciencias CO-111321 Bogota Colombia Santa Fe Inst Santa Fe NM 87501 USA

Best match graphs (BMGs) are vertex-colored digraphs that naturally arise in mathematical phylogenetics to formalize the notion of evolutionary closest genes w.r.t. an a priori unknown phylogenetic tree. BMGs are explained by unique least resolved trees. We prove that the property of a rooted, leaf-colored tree to be least resolved for some BMG is preserved by the contraction of inner edges. For the special case of two-colored BMGs, this leads to a characterization of the least resolved trees (LRTs) of binary-explainable trees and a simple, polynomial-time algorithm for the minimum cardinality completion of the arc set of a BMG to reach a BMG that can be explained by a binary tree.

关键词： best matches least resolved trees graph completion polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

An

引用

SIAM Journal on Computing 1978年第2期7卷 154-157页

作者： Nimrod Megiddo Arie Tamir

The following class of matching problems is considered. The vertices of a complete undirected graph are indexed 1,⋯,n1,⋯,n1, \cdots,n, where <span class="MathJax" id="MathJax-Element-5-Frame" ta... 详细信息

The following class of matching problems is considered. The vertices of a complete undirected graph are indexed

1, \dots, n

$1, \cdots,n$ , where

matching assignment scheduling polynomial-time algorithm 2-3 trees

来源：评论

学校读者我要写书评

暂无评论

Adapting Stable Matchings to Forced and Forbidden Pairs 23

Adapting Stable Matchings to Forced and Forbidden Pairs

引用

Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems

作者： Niclas Boehmer Klaus Heeger Technische Universität Berlin Berlin Germany

ISBN: (纸本)9781450394321

We introduce the problem of adapting a stable matching to forced and forbidden pairs. Specifically, given a stable matching M1, a set Q of forced pairs, and a set P of forbidden pairs, we want to find a stable matching that includes all pairs from Q, no pair from P, and that is as close as possible to M1. We study this problem in four classical stable matching settings: Stable Roommates (with Ties) and Stable Marriage (with Ties).As our main contribution, we employ the theory of rotations for Stable Roommates to develop a polynomial-time algorithm for adapting Stable Roommates matchings to forced pairs. In contrast to this, we show that the same problem for forbidden pairs is NP-hard. However, our polynomial-time algorithm for the case of only forced pairs can be extended to a fixed-parameter tractable algorithm with respect to the number of forbidden pairs when both forced and forbidden pairs are present. Moreover, we also study the setting where preferences contain ties. Here, depending on the chosen stability criterion, we show either that our algorithmic results can be extended or that formerly tractable problems become intractable.

关键词： FPT NP-hardness incremental algorithms W[1]-hardness forced and forbidden pairs polynomial-time algorithm stable marriage rotations stable roommates

来源：评论

学校读者我要写书评

暂无评论

Matching problems with delta-matroid constraints 12

Matching problems with delta-matroid constraints

引用

Proceedings of the Eighteenth Computing: The Australasian Theory Symposium - Volume 128

作者： Naonori Kakimura Mizuyo Takamatsu University of Tokyo Tokyo Japan Chuo University Tokyo Japan

ISBN: (纸本)9781921770098

Given an undirected graph G = (V, E) and a directed graph D = (V, A), the master/slave matching problem is to find a matching of maximum cardinality in G such that for each arc (u, v) ε A with u being matched, v is also matched. This problem is known to be NP-hard in general, but polynomially solvable in a special case where the maximum size of a connected component of D is at most *** paper investigates the master/slave matching problem in terms of delta-matroids, which is a generalization of matroids. We first observe that the above polynomially solvable constraint can be interpreted as delta-matroids. We then introduce a new class of matching problem with delta-matroid constraints, which can be solved in polynomial time. In addition, we discuss our problem with additional constraints such as capacity constraints.

关键词： mixed matrix theory polynomial-time algorithm constrained matching delta-matroid

来源：评论

学校读者我要写书评

暂无评论

A polynomial algorithm to find an independent set of maximum weight in a fork-free graph 06

A polynomial algorithm to find an independent set of maximum...

引用

Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm

作者： Vadim V. Lozin Martin Milanič Rutgers University Piscataway NJ

ISBN: (纸本)9780898716054

The class of fork-free graphs is an extension of claw-free graphs and their subclass of line graphs. The first polynomial-time solution to the maximum weight independent set problem in the class of line graphs, which is equivalent to the maximum matching problem in general graphs, has been proposed by Edmonds in 1965 and then extended to the entire class of claw-free graphs by Minty in 1980. Recently, Alekseev proposed a solution for the larger class of fork-free graphs, but only for the unweighted version of the problem, i.e. finding an independent set of maximum cardinality. In the present paper, we describe the first polynomial-time algorithm to solve the problem for weighted fork-free graphs.

关键词： independent set polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：