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

Connected Vertex Cover for (sP1 + P5)-Free Graphs

algorithmICA 2020年第1期82卷 20-40页

作者： Johnson, Matthew Paesani, Giacomo Paulusma, Daniel Univ Durham Dept Comp Sci Durham England

The Connected Vertex Cover problem is to decide if a graph G has a vertex cover of size at most k that induces a connected subgraph of G. This is a well-studied problem, known to be NP-complete for restricted graph classes, and, in particular, for H-free graphs if H is not a linear forest. On the other hand, the problem is known to be polynomial-time solvable for sP(2)-free graphs for any integer s >= 1. We give a polynomial-time algorithm to solve the problem for (sP(1)+P-5)-free graphs for every integer s >= 0. Our algorithm can also be used for the WEIGHTED CONNECTED VERTEX COVER problem.

关键词： Vertex cover Connected vertex cover H-free graph polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A semi-"smart predict then optimize" (semi-SPO) method for efficient ship inspection

引用

TRANSPORTATION RESEARCH PART B-METHODOLOGICAL 2020年 142卷 100-125页

作者： Yan, Ran Wang, Shuaian Fagerholt, Kjetil Hong Kong Polytech Univ Dept Logist & Maritime Studies Hung Hom Kowloon Hong Kong Peoples R China Norwegian Univ Sci & Technol Dept Ind Econ & Technol Management Trondheim Norway

Efficient inspection of ships at ports to ensure their compliance with safety and environmental regulations is of vital significance to maritime transportation. Given that maritime authorities often have limited inspection resources, we proposed three two-step approaches that match the inspection resources with the ships, aimed at identifying the most deficiencies (non-compliances with regulations) of the ships. The first approach predicts the number of deficiencies in each deficiency category for each ship and then develops an integer optimization model that assigns the inspectors to the ships to be inspected. The second approach predicts the number of deficiencies each inspector can identify for each ship and then applies an integer optimization model to assign the inspectors to the ships to be inspected. The third approach is a semi-"smart predict then optimize" (semi-SPO) method. It also predicts the number of deficiencies each inspector can identify for each ship and uses the same integer optimization model as the second approach, however, instead of minimizing the mean squared error as in the second approach, it adopts a loss function motivated by the structure of the optimization problem in the second approach. Numerical experiments show that the proposed approaches improve the current inspection efficiency by over 4% regarding the total number of detected deficiencies. Through comprehensive sensitivity analysis, several managerial insights are generated and the robustness of the proposed approaches is validated. (c) 2020 Elsevier Ltd. All rights reserved.

关键词： Maritime transportation Tree-based prediction models polynomial-time algorithm Ship inspection Smart predict then optimize (SPO)

来源：评论

学校读者我要写书评

暂无评论

CLOSED FORM OF THE RESPONSE FUNCTION IN FDH TECHNOLOGIES: THEORY, COMPUTATION AND APPLICATION

引用

RAIRO-OPERATIONS RESEARCH 2020年第1期54卷 53-68页

作者： Mostafaee, Amin Soleimani-Damaneh, Majid Islamic Azad Univ Coll Sci Dept Math Tehran North Branch Tehran Iran Univ Tehran Coll Sci Sch Math Stat & Comp Sci Enghelab Ave Tehran Iran

Response function (RF), which gives the value of maximum feasible outputs in response to changing the inputs, has a crucial role in performance analysis and scale elasticity measurement. In this paper, a polynomial-time algorithm is provided which is able to obtain the closed form of the RF under (nonconvex) FDH productions technologies. Finite convergence of the presented algorithm is proved;and it is established that the algorithm is polynomial-time from a complexity standpoint. Moreover, an application of the proposed procedure with real-world data accompanying some experiment-based computational discussions are given.

关键词： Data envelopment analysis FDH technologies response function polynomial-time algorithm real application computational experiments

来源：评论

学校读者我要写书评

暂无评论

On Polyatomic Tomography over Abelian Groups: Some Remarks on Consistency, Tree Packings and Complexity

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2020年第2期64卷 290-303页

作者： Gritzmann, Peter Langfeld, Barbara Tech Univ Munich Zentrum Math D-85747 Garching Germany Christian Albrechts Univ Kiel Math Seminar D-24118 Kiel Germany

The paper deals with an inverse problem of reconstructing matrices from their marginal sums. More precisely, we are interested in the existence of rxsmatrices for which only the following information is available: The entries belong to known subsets of c distinguishable abelian groups, and the row and column sums of all entries from each group are given. This generalizes Ryser's classical problem of characterizing the set of all 0-1-matrices with given row and column sums and is a basic problem in (polyatomic) discrete tomography. We show that the problem is closely related to packings of trees in bipartite graphs, prove consistency results, give algorithms and determine its complexity. In particular, we find a somewhat unusual complexity behavior: the problem is hard for "small" but easy for "large" matrices.

关键词： Discrete inverse problem Discrete tomography Polyatomic tomography polynomial-time algorithm NP-completeness

来源：评论

学校读者我要写书评

暂无评论

Two-closures of supersolvable permutation groups in polynomial time

引用

COMPUTATIONAL COMPLEXITY 2020年第1期29卷 1-33页

作者： Ponomarenko, Ilia Vasil'ev, Andrey Steklov Inst Math St Petersburg St Petersburg Russia Sobolev Inst Math Novosibirsk Russia Novosibirsk State Univ Novosibirsk Russia

The 2-closure (G) over bar of a permutation group G on Omega is defined to be the largest permutation group on Omega, having the same orbits on Omega x Omega as G. It is proved that if G is supersolvable, then (G) over bar can be found in polynomial time in vertical bar Omega vertical bar. As a by-product of our technique, it is shown that the composition factors of (G) over bar are cyclic or alternating.

关键词： Permutation group 2-closure polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Maximizing the strong triadic closure in split graphs and proper interval graphs

引用

DISCRETE APPLIED MATHEMATICS 2020年 285卷 79-95页

作者： Konstantinidis, Athanasios L. Papadopoulos, Charis Univ Ioannina Dept Math Ioannina Greece

In social networks the STRONG TRIADIC CLOSURE is an assignment of the edges with strong or weak labels such that any two vertices that have a common neighbor with a strong edge are adjacent. The problem of maximizing the number of strong edges that satisfy the strong triadic closure was recently shown to be NP-complete for general graphs. Here we initiate the study of graph classes for which the problem is solvable. We show that the problem admits a polynomial-time algorithm for two incomparable classes of graphs: proper interval graphs and trivially-perfect graphs. To complement our result, we show that the problem remains NP-complete on split graphs, and consequently also on chordal graphs. Thus, we contribute to define the first border between graph classes on which the problem is polynomially solvable and on which it remains NP-complete. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Strong triadic closure polynomial-time algorithm NP-completeness Split graphs Proper interval graphs

来源：评论

学校读者我要写书评

暂无评论

Single machine batch scheduling with two non-disjoint agents and splitable jobs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2020年第3期40卷 774-795页

作者： Geng, Zhichao Liu, Jiayu Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China Henan Coll Transportat Zhengzhou 450001 Henan Peoples R China

We investigate the scheduling problem on a single bounded parallel-batch machine where jobs belong to two non-disjoint agents (called agent A and agent B) and are of equal length but different size. Each job's size can be arbitrarily split into two parts and processed in the consecutive batches. It is permitted to process the jobs from different agents in a common batch. We show that it is unary NP-hard for the problem of minimizing the total weighted completion time of the jobs of agent A subject to the maximum cost of the jobs of agent B being upper bounded by a given threshold. For the case of the jobs of agent A having identical weights, we study the version of Pareto problem, and give a polynomial-time algorithm to generate all Pareto optimal points and a Pareto optimal schedule corresponding to each Pareto optimal point.

关键词： Parallel-batch Splitable jobs Pareto optimal polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Disconnected cuts in claw-free graphs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2020年 113卷 60-75页

作者： Martin, Barnaby Paulusma, Daniel van Leeuwen, Erik Jan Univ Durham Durham England Univ Utrecht Utrecht Netherlands

A disconnected cut of a connected graph is a vertex cut that itself also induces a disconnected subgraph. The corresponding decision problem is called DISCONNECTED CUT. This problem is known to be NP-hard on general graphs. We prove that it is polynomialtime solvable on claw-free graphs, answering a question of Ito et al. (TCS 2011). The basis for our result is a decomposition theorem for claw-free graphs of diameter 2, which we believe is of independent interest and builds on the research line initiated by Chudnovsky and Seymour (JCTB 2007-2012) and Hermelin et al. (ICALP 2011). On our way to exploit this decomposition theorem, we characterize how disconnected cuts interact with certain cobipartite subgraphs, and prove two further algorithmic results, namely that DISCONNECTED CUT is polynomial-time solvable on circular-arc graphs and line graphs. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Vertex cut Claw-free graph Line graph Circular-arc graph Graph decomposition polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

algorithms for Distributed Server Allocation Problem

引用

IEICE TRANSACTIONS ON COMMUNICATIONS 2020年第11期E103B卷 1341-1352页

作者： Sawa, Takaaki He, Fujun Kawabata, Akio Oki, Eiji Kyoto Univ Grad Sch Informat Kyoto 6068501 Japan NTT Network Technol Labs Tokyo 1808585 Japan

This paper proposes two algorithms, namely Server-User Matching (SUM) algorithm and Extended Server-User Matching (ESUM) algorithm, for the distributed server allocation problem. The server allocation problem is to determine the matching between servers and users to minimize the maximum delay, which is the maximum time to complete user synchronization. We analyze the computational time complexity. We prove that the SUM algorithm obtains the optimal solutions in polynomial time for the special case that all server-server delay values are the same and constant. We provide the upper and lower bounds when the SUM algorithm is applied to the general server allocation problem. We show that the ES UM algorithm is a fixed-parameter tractable algorithm that can attain the optimal solution for the server allocation problem parameterized by the number of servers. Numerical results show that the computation time of ESUM follows the analyzed complexity while the ESUM algorithm outperforms the approach of integer linear programming solved by our examined solver.

关键词： distributed processing server allocation problem polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Subset feedback vertex set on graphs of bounded independent set size

引用

THEORETICAL COMPUTER SCIENCE 2020年 814卷 177-188页

作者： Papadopoulos, Charis Tzimas, Spyridon Univ Ioannina Dept Math Ioannina Greece

The (WEIGHTED) SUBSET FEEDBACK VERTEX SET problem is a generalization of the classical FEEDBACK VERTEX SET problem and asks for a vertex set of minimum (weight) size that intersects all cycles containing a vertex of a predescribed set of vertices. Although SUBSET FEEDBACK VERTEX SET and FEEDBACK VERTEX SET exhibit different computational complexity on split graphs, no similar characterization is known on other classes of graphs. Towards the understanding of the complexity difference between the two problems, it is natural to study the importance of structural graph parameters. Here we consider graphs of bounded independent set number for which it is known that WEIGHTED FEEDBACK VERTEX SET can be solved in polynomial time. We provide a dichotomy result with respect to the size alpha OF a maximum independent set. In particular we show that WEIGHTED SUBSET FEEDBACK VERTEX SET can be solved in polynomial time for graphs with alpha <= 3, whereas we prove that the problem remains NP-hard for graphs with alpha >= 4. Moreover, we show that the (unweighted) SUBSET FEEDBACK VERTEX SET problem can be solved in polynomial time on graphs of bounded independent set number by giving an algorithm with running time n(O)(alpha). To complement our results, we demonstrate how our ideas can be extended to other terminal set problems on graphs of bounded independent set size. NODE MULTIWAY CUT is a terminal set problem that asks for a vertex set of minimum size that intersects all paths connecting any two terminals. Based on our findings for SUBSET FEEDBACK VERTEX SET, we settle the complexity of NODE MULTIWAY CUT as well as its variants where nodes are weighted and/or the terminals are deletable, for every value of the given independent set number. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Subset feedback vertex set Node multiway cut polynomial-time algorithm NPcompleteness W[1]-hardness Graphs of bounded independent set size

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：