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

Linear Arboricity of Outer-1-Planar Graphs

Journal of the Operations Research Society of China 2021年第1期9卷 181-193页

作者： Xin Zhang Bi Li School of Mathematics and Statistics Xidian UniversityXi’an 710071China

A graph is outer-1-planar if it can be drawn in the plane so that all vertices are on the outer face and each edge is crossed at most *** et al.(Edge covering pseudo-outerplanar graphs with forests,Discrete Math 312:2788-2799,2012;MR2945171)proved that the linear arboricity of every outer-1-planar graph with maximum degree△is exactly[△/2] provided that△=3or△≥5 and claimed that there are outer-1-planar graphs with maximum degree △=4 and linear arboricity[[(O+1)/2]=*** is shown in this paper that the linear arboricity of every outer-1-planar graph with maximum degree 4 is exactly 2 provided that it admits an outer-1-planar drawing with crossing distance at least 1 and crossing width at least 2,and moreover,none of the above constraints on the crossing distance and Crossing width can be removed..Besides,a polynomial-time algorithm for constructing a path-2-coloring(i.e.,an edge 2-coloring such that each color class induces a linear forest,a disjoint union of paths)of such an outer-1-planar drawing is given.

关键词： Outer-1-planar graph Crossing Linear arboricity polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

The Complexity of Growing a Graph 1

引用

18th International Symposium on algorithmics of Wireless Networks

作者： Mertzios, George B. Michail, Othon Skretas, George Spirakis, Paul G. Theofilatos, Michail Univ Durham Dept Comp Sci Durham England Univ Liverpool Dept Comp Sci Liverpool Merseyside England Univ Potsdam Hasso Plattner Inst Potsdam Germany Univ Patras Comp Engn & Informat Dept Patras Greece

ISBN: (数字)9783031220500

ISBN: (纸本)9783031220494;9783031220500

We study a new algorithmic process of graph growth. The process starts from a single initial vertex u(0) and operates in discrete time-steps, called slots. In every slot t >= 1, the process updates the current graph instance to generate the next graph instance G(t). The process first sets G(t) = G(t-1). Then, for every u is an element of V (G(t-1)), it adds at most one new vertex u' to V (G(t)) and adds the edge uu' to E(G(t)) alongside any subset of the edges {vu' vertical bar v is an element of V (G(t-1)) is at distance at most d - 1 from u in G(t-1)}, for some integer d >= 1 fixed in advance. The process completes slot t after removing any (possibly empty) subset of edges from E(G(t)). Removed edges are called excess edges. G(t) is the graph grown by the process after t slots. The goal of this paper is to investigate the algorithmic and structural properties of this process of graph growth. Graph Growth Problem: Given a graph family F, we are asked to design a centralized algorithm that on any input target graph G is an element of F, will output such a process growing G, called a growth schedule for G. Additionally, the algorithm should try to minimize the total number of slots k and of excess edges l used by the process. We show that the most interesting case is when d = 2 and that there is a natural trade-off between k and l. We begin by investigating growth schedules of l = 0 excess edges. On the positive side, we provide polynomial-time algorithms that decide whether a graph has growth schedules of k = logn or k = n - 1 slots. Along the way, interesting connections to cop-win graphs are being revealed. On the negative side, we establish strong hardness results for the problem of determining the minimum number of slots required to grow a graph with zero excess edges. In particular, we show that the problem (i) is NP-complete and (ii) for any e > 0, cannot be approximated within n(1/3-epsilon), unless P = NP. We then move our focus to the other extreme of the (

关键词： Temporal graph Cop-win graph Graph process polynomial-time algorithm Lower bound NP-complete Hardness result

来源：评论

学校读者我要写书评

暂无评论

The single train shortest route problem in a railyard

引用

OPTIMIZATION LETTERS 2021年第8期15卷 2577-2595页

作者： Aliakbari, Mina Geunes, Joseph Sullivan, Kelly M. Texas A&M Univ Dept Ind & Syst Engn College Stn TX 77843 USA Univ Arkansas Dept Ind Engn Fayetteville AR 72701 USA

We consider the problem of moving a connected set of railcars, which we refer to as a train, from an origin layout to a destination layout in a railyard, accounting for the special structure of the railyard network and the length and orientation of the train. We propose a novel shortest path algorithm for determining a sequence of moves that minimizes the total distance (and associated time) required to move a train from its origin to destination. A railyard network consists of a set of track sections connected via switch points, which correspond to points at which three sections of track come together, such that one pair of the track segments forms an acute angle (and the other two pairs form obtuse angles). A train's ability to traverse a switch node depends on the train's length and whether or not its desired route involves traversing the acute angle or an obtuse angle at the switch. The shortest route problem for a train is further complicated by the fact that a train's position on the network at any point in time may span multiple nodes in the network. We propose an easily explained solution approach that addresses the complications associated with switch points and the train's length to determine a shortest route from origin to destination in O(e + n log n) operations, where n and e correspond to the number of switch nodes and edges in the network respectively.

关键词： Shortest path Railyard network Routing polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Strong cliques in diamond-free graphs

引用

THEORETICAL COMPUTER SCIENCE 2021年 858卷 49-63页

作者： Chiarelli, Nina Martinez-Barona, Berenice Milanic, Martin Monnot, Jerome Mursic, Peter Univ Primorska FAMNIT Glagoljaska 8 Koper 6000 Slovenia Univ Primorska IAM Muzejski Trg 2 Koper 6000 Slovenia Univ Politecn Cataluna Dept Engn Civil & Ambiental Barcelona Spain Univ Paris 09 LAMSADE Paris 16 France

A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets. Strong cliques play an important role in the study of perfect graphs. We study strong cliques in the class of diamond-free graphs, from both structural and algorithmic points of view. We show that the following five NP-hard or co-NP-hard problems all remain NP-hard or coNP-hard when restricted to the class of diamond-free graphs: Is a given clique strong? Does the graph have a strong clique? Is every vertex contained in a strong clique? Given a partition of the vertex set into cliques, is every clique in the partition strong? Can the vertex set be partitioned into strong cliques? On the positive side, we show that the following three problems whose computational complexity is open in general can be solved in polynomial time in the class of diamondfree graphs: Does every induced subgraph have a strong clique? Is every maximal clique strong? Is every edge contained in a strong clique? The last two results are derived from a characterization of diamond-free graphs in which every maximal clique is strong, which also implies an improved Erd os-Hajnal property for such graphs. (c) 2020 Elsevier B.V. All rights reserved.

关键词： Maximal clique Maximal stable set Diamond-free graph Strong clique Simplicial clique Strongly perfect graph CIS graph NP-hard problem polynomial-time algorithm Erdos-Hajnal property

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Wasserstein Barycenters can be Computed in polynomial time in Fixed Dimension

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2021年第1期22卷 1-19页

作者： Altschuler, Jason M. Boix-Adsera, Enric MIT Lab Informat & Decis Syst 77 Massachusetts Ave Cambridge MA 02139 USA

Computing Wasserstein barycenters is a fundamental geometric problem with widespread applications in machine learning, statistics, and computer graphics. However, it is unknown whether Wasserstein barycenters can be computed in polynomial time, either exactly or to high precision (i.e., with polylog(1/epsilon) runtime dependence). This paper answers these questions in the affirmative for any fixed dimension. Our approach is to solve an exponential-size linear programming formulation by efficiently implementing the corresponding separation oracle using techniques from computational geometry.

关键词： Wasserstein barycenters free support polynomial-time algorithm exponential-size linear program power diagrams

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Complete Characterization of Incorrect Orthology Assignments in Best Match Graphs

引用

JOURNAL OF MATHEMATICAL BIOLOGY 2021年第3期82卷 1-64页

作者： Schaller, David Geiss, Manuela Stadler, Peter F. Hellmuth, Marc Max Planck Inst Math Sci Inselstr 22 D-04103 Leipzig Germany Univ Leipzig Dept Comp Sci Bioinformat Grp Hartelstr 16-18 D-04107 Leipzig Germany Univ Leipzig Interdisciplinary Ctr Bioinformat Hartelstr 16-18 D-04107 Leipzig Germany Software Competence Ctr Hagenberg GmbH Softwarepk 21 A-4232 Hagenberg Austria Univ Leipzig Dept Comp SciInterdisciplinary Ctr Bioinformat German Ctr Integrat Biodivers Res IDiv Halle Jena Bioinformat GrpCompetence Ctr Scalable Data Serv Hartelstr 16-18 D-04107 Leipzig Germany Univ Leipzig Leipzig Res Ctr Civilizat Dis Hartelstr 16-18 D-04107 Leipzig Germany Univ Vienna Inst Theoret Chem Wahringerstr 17 A-1090 Vienna Austria Univ Nacl Colombia Fac Ciencias Bogota Colombia Santa Fe Inst 1399 Hyde Pk Rd Santa Fe NM 87501 USA Stockholm Univ Dept Math Fac Sci SE-10691 Stockholm Sweden

Genome-scale orthology assignments are usually based on reciprocal best matches. In the absence of horizontal gene transfer (HGT), every pair of orthologs forms a reciprocal best match. Incorrect orthology assignments therefore are always false positives in the reciprocal best match graph. We consider duplication/loss scenarios and characterize unambiguous false-positive (u-fp) orthology assignments, that is, edges in the best match graphs (BMGs) that cannot correspond to orthologs for any gene tree that explains the BMG. Moreover, we provide a polynomial-time algorithm to identify all u-fp orthology assignments in a BMG. Simulations show that at least 75% of all incorrect orthology assignments can be detected in this manner. All results rely only on the structure of the BMGs and not on any a priori knowledge about underlying gene or species trees.

关键词： Orthology detection Best matches Unambiguous orthologs Colored graphs Cograph Tree reconciliation polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Feedback vertex set reconfiguration in planar graphs

引用

THEORETICAL COMPUTER SCIENCE 2023年 979卷

作者： Bousquet, Nicolas Hommelsheim, Felix Kobayashi, Yusuke Muehlenthaler, Moritz Suzuki, Akira Univ Lyon 1 Univ Lyon CNRS LIRISUMR 5205 Lyon France Univ Bremen Fac Math & Comp Sci Bremen Germany Kyoto Univ Res Inst Math Sci Kyoto Japan Univ Grenoble Alpes Lab G SCOP Grenoble France Tohoku Univ Grad Sch Informat Sci Sendai Japan

We study the complexity of deciding whether for two given feedback vertex sets of a graph there is a step-by-step transformation between them, such that for each feedback vertex set in the transformation, the next one is obtained by exchanging a single vertex. We give a classification of the complexity of this question for planar graphs in terms of the maximum degree. We show that for planar graphs of maximum degree at most three the problem is tractable because there always exists a transformation, while it is PSPACE-complete when the maximum degree is at most four. The positive side of the classification extends to K-3,K-3-minor-free graphs of maximum degree three. We then consider the Matroid Parity problem, which generalizes feedback vertex sets in graphs of maximum degree three as well as matchings and spanning trees in general graphs. Generalizing known results for the latter two we show that there always exists a transformation between any two non -maximum independent parity sets.(c) 2023 Elsevier B.V. All rights reserved.

关键词： Feedback vertex set Combinatorial reconfiguration polynomial-time algorithm Planar graph Matroid parity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：