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

25th International Conference on Integer Programming and Combinatorial Optimization (IPCO)

作者： Mizutani, Ryuhei Yoshida, Yuki Univ Tokyo Tokyo 1138656 Japan

ISBN: (纸本)9783031598340;9783031598357

It is a fundamental result in combinatorial optimization that submodular functions can be minimized in polynomial-time. This paper considers the minimization problem for a more general class of set functions that contains all submodular functions. A set function is called 2/3-submodular if the submodular inequality holds for at least two pairs formed from every distinct three subsets. This paper provides two weakly polynomial-time algorithms to minimize 2/3-submodular functions, which yield an efficient algorithm to obtain color assignments of a variant of the supermodular coloring theorem.

关键词： 2/3-submodular function polynomial-time algorithm Supermodular coloring

来源：评论

学校读者我要写书评

暂无评论

polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers

Polynomial-time Isomorphism Test for Groups with Abelian Syl...

引用

29th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Babai, Laszlo Qiao, Youming Univ Chicago Dept Comp Sci Chicago IL 60637 USA Tsinghua Univ Inst Interdisciplinary Informat Sci Beijing Peoples R China

ISBN: (纸本)9783939897354

We consider the problem of testing isomorphism of groups of order n given by Cayley tables. The trivial n(log) (n) bound on the time complexity for the general case has not been improved over the past four decades. Recently, Babai et al. (following Babai et al. in SODA 2011) presented a polynomial-time algorithm for groups without abelian normal subgroups, which suggests solvable groups as the hard case for group isomorphism problem. Extending recent work by Le Gall (STACS 2009) and Qiao et al. (STACS 2011), in this paper we design a polynomial-time algorithm to test isomorphism for the largest class of solvable groups yet, namely groups with abelian Sylow towers, defined as follows. A group G is said to possess a Sylow tower, if there exists a normal series where each quotient is isomorphic to a Sylow subgroup of G. A group has an abelian Sylow tower if it has a Sylow tower and all its Sylow subgroups are abelian. In fact, we are able to compute the coset of isomorphisms of groups formed as coprime extensions of an abelian group, by a group whose automorphism group is known. The mathematical tools required include representation theory, Wedderburn's theorem on semisimple algebras, and M.E. Harris's 1980 work on p'-automorphisms of abelian p-groups. We use tools from the theory of permutation group algorithms, and develop an algorithm for a parameterized version of the graph-isomorphism-hard setwise stabilizer problem, which may be of independent interest.

关键词： polynomial-time algorithm group isomorphism solvable group

来源：评论

学校读者我要写书评

暂无评论

Detecting Protected Links to Keep Reachability to Server against Failures

Detecting Protected Links to Keep Reachability to Server aga...

引用

27th International Conference on Information Networking (ICOIN)

作者： Imagawa, Koji Miwa, Hiroyoshi Kwansei Gakuin Univ Grad Sch Sci & Technol Nishinomiya Hyogo 6691337 Japan

ISBN: (纸本)9781467357425;9781467357401

Methods to design a reliable network against network failures are important for Internet service providers (ISPs). ISPs must offer connectivity to users, even if link failures occur. The best way to design a reliable network is to protect all links so that the failure probability of a link is sufficiently small by sufficient backup resource and rapid recovery system. However, sufficient backup resource needs much cost for ISP. Therefore, it is necessary to find the smallest number of links to be protected such that, even if any non-protected links fail, the resulting network offers users connectivity. In this paper, as a measure of connectivity, we focus on the size of the connected component including a server or a gateway. Critical links whose failures drastically decrease the size of the connected component including a server must be protected not to fail, because such a failure prevent a large number of users from access to the server. Similarly, when a server is a gateway to another ISP's network, many users cannot communicate with exterior users and servers. Our purpose is to find the links to be protected such that, even if any non-protected links fail, the number of the nodes connected with a server in the resulting network is not less than a threshold. In this paper, we formulate this problem and prove that the problem is NP-hard. In addition, we propose a polynomial-time algorithm to solve the problem that the number of the simultaneous link failures is restricted to one. Furthermore, we present a polynomial-time algorithm to solve the problem that the number of the simultaneous link failures is restricted to two and a network is a tree.

关键词： link protection network design reachability optimization NP-hard polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Single Track Transportation in a Two-Machine Production System 10th

Single Track Transportation in a Two-Machine Production Syst...

引用

10th IFAC Triennial Conference on Manufacturing Modelling, Management and Control (MIM)

作者： Zinder, Yakov Lazarev, Alexander Musatova, Elena Univ Technol Sydney NSW Australia Russian Acad Sci VA Trapeznikov Inst Control Sci 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. Copyright (C) 2022 The Authors.

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

来源：评论

学校读者我要写书评

暂无评论

THE k-IN-A-PATH PROBLEM FOR CLAW-FREE GRAPHS

THE <i>k</i>-IN-A-PATH PROBLEM FOR CLAW-FREE GRAPHS

引用

27th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Fiala, Jiri Kaminski, Marcin Lidicky, Bernard Paulusma, Daniel Charles Univ Prague Fac Math & Phys DIMATIA Malostranske Nam 2-25 CR-18000 Prague Czech Republic Inst Theoret Comp Sci ITI CR-18000 Prague Czech Republic Univ Libre Bruxelles Dept Comp Sci B-1050 Brussels Belgium Univ Durham Dept Comp Sci Sci Labs Durham DH1 3LE England

Testing whether there is an induced path in a graph spanning k given vertices is already NP-complete in general graphs when k = 3. We show how to solve this problem in polynomial time on claw-free graphs, when k is no... 详细信息

ISBN: (纸本)9783939897163

关键词： induced path claw-free graph polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

AWeighted Linear Matroid Parity algorithm 2017

AWeighted Linear Matroid Parity Algorithm

引用

49th Annual ACM-SIGACT Symposium on Theory of Computing (STOC)

作者： Iwata, Satoru Kobayashi, Yusuke Univ Tokyo Tokyo 1138656 Japan Univ Tsukuba Tsukuba Ibaraki 3058573 Japan

ISBN: (纸本)9781450345286

The matroid parity (or matroid matching) problem, introduced as a common generalization of matching and matroid intersection problems, is so general that it requires an exponential number of oracle calls. Lovasz (1980) showed that this problem admits a minmax formula and a polynomial algorithm for linearly represented matroids. Since then efficient algorithms have been developed for the linear matroid parity problem. In this paper, we present a combinatorial, deterministic, polynomialtime algorithm for the weighted linear matroid parity problem. The algorithm builds on a polynomial matrix formulation using Pfaffian and adopts a primal-dual approach based on the augmenting path algorithm of Gabow and Stallmann (1986) for the unweighted problem.

关键词： Linear matroid parity matching polynomial-time algorithm Pfaf-fian primal-dual approach

来源：评论

学校读者我要写书评

暂无评论

An O(n²) algorithm for a controllable machine scheduling problem

引用

IMA Journal of Management Mathematics 1999年第1期10卷 15-26页

作者： Huang, Wanzhen Zhang, Feng Department of Mathematics and Statistics School of Mathematical Sciences Lakehead University ON P7B 5E1 Canada Department of Applied Mathematics Shanghai Second Polytechnic University China

A single-machine scheduling problem with controllable processing times is discussed in this paper. For some jobs, the processing time can be crashed up to u units of time with the additional cost c per unit of time crashed. The object is to find an optimal processing sequence as well as crash activities to minimize total costs of completion and crash. This problem is shown to be polynomially solvable, and an O(n²) algorithm is given together with the theoretical proof. © Oxford University Press 1999.

关键词： Controllable processing times Crash activities polynomial-time algorithm Single-machine scheduling problems

来源：评论

学校读者我要写书评

暂无评论

Edge search number of cographs

Edge search number of cographs

引用

4th Workshop on Graph Classes, Optimization, and Width Parameters (GROW)

作者： Golovach, Petr A. Heggernes, Pinar Mihai, Rodica Univ Bergen Dept Informat N-5020 Bergen Norway Univ Durham Sch Engn & Comp Sci Durham DH1 3LE England

We give a linear-time algorithm for computing the edge search number of cographs, thereby resolving the computational complexity of edge searching on this graph class. To achieve this we give a characterization of the edge search number of the join of two graphs. With our result, the knowledge on graph searching of cographs is now complete: node, mixed, and edge search numbers of cographs can all be computed efficiently. Furthermore, we are one step closer to computing the edge search number of permutation graphs. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Graph searching NP-hard problem polynomial-time algorithm Graph classes Cographs

来源：评论

学校读者我要写书评

暂无评论

A Fast algorithm for Reconstructing hv-Convex Binary Images from Their Horizontal Projection 10

A Fast Algorithm for Reconstructing <i>hv</i>-Convex Binary ...

引用

10th International Symposium on Visual Computing (ISVC)

作者： Hantos, Norbert Balazs, Peter Eotvos Lorand Univ Dept Algorithms & Their Applicat H-1117 Budapest Hungary Univ Szeged Dept Image Proc & Comp Graph H-6720 Szeged Hungary

ISBN: (纸本)9783319143644;9783319143637

The reconstruction of certain types of binary images from their projections is a frequently studied problem in combinatorial image processing. hv-convex images with fixed projections play an important role in discrete tomography. In this paper, we provide a fast polynomialtime algorithm for reconstructing canonical hv-convex images with given number of 4-connected components and with minimal number of columns satisfying a prescribed horizontal projection. We show that the method gives a solution that is always 8-connected. We also explain how the algorithm can be modified to obtain solutions with any given number of columns, and also with non-connected components.

关键词： discrete tomography reconstruction connectedness hv-convexity polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Finding Induced Paths of Given Parity in Claw-Free Graphs

引用

algorithmICA 2012年第1-2期62卷 537-563页

作者： van 't Hof, Pim Kaminski, Marcin Paulusma, Daniel Univ Durham Sch Engn & Comp Sci Sci Labs Durham DH1 3LE England Univ Libre Bruxelles Dept Comp Sci B-1050 Brussels Belgium

The Parity Path problem is to decide if a given graph contains both an induced path of odd length and an induced path of even length between two specified vertices. In the related problems Odd Induced Path and Even Induced Path, the goal is to determine whether an induced path of odd, respectively even, length between two specified vertices exists. Although all three problems are NP-complete in general, we show that they can be solved in O(n(5)) time for the class of claw-free graphs. Two vertices s and t form an even pair in G if every induced path from s to t in G has even length. Our results imply that the problem of deciding if two specified vertices of a claw-free graph form an even pair, as well as the problem of deciding if a given claw-free graph has an even pair, can be solved in O(n(5)) time and O(n(7)) time, respectively. We also show that we can decide in O(n(7)) time whether a claw-free graph has an induced cycle of given parity through a specified vertex. Finally, we show that a shortest induced path of given parity between two specified vertices of a claw-free perfect graph can be found in O(n(7)) time.

关键词： Induced path Parity path Claw-free graph polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：