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

5th International Symposium on Combinatorial Optimization (ISCO)

作者： Chiarelli, Nina Hartinger, Tatiana Romina Alejandra Leoni, Valeria Lopez Pujato, Maria Ines Milanic, Martin Univ Primorska FAMNIT Glagoljaska 8 Koper 6000 Slovenia Univ Primorska IAM Muzejski Trg 2 Koper 6000 Slovenia Univ Nacl Rosario FCEIA Rosario Santa Fe Argentina Consejo Nacl Invest Cient & Tecn Buenos Aires DF Argentina ANPCyT Buenos Aires DF Argentina

ISBN: (纸本)9783319961514;9783319961507

Given a positive integer k, a k-dominating set in a graph G is a set of vertices such that every vertex not in the set has at least k neighbors in the set. A total k-dominating set, also known as a k-tuple total dominating set, is a set of vertices such that every vertex of the graph has at least k neighbors in the set. The problems of finding the minimum size of a k-dominating, resp. total k-dominating set, in a given graph, are referred to as k-domination, resp. total k-domination. These generalizations of the classical domination and total domination problems are known to be NP-hard in the class of chordal graphs, and, more specifically, even in the classes of split graphs (both problems) and undirected path graphs (in the case of total k-domination). On the other hand, it follows from recent work by Kang et al. (2017) that these two families of problems are solvable in time O(vertical bar V(G)vertical bar(6k+4)) in the class of interval graphs. In this work, we develop faster algorithms for k-domination and total k-domination in the class of proper interval graphs. The algorithms run in time O(vertical bar V(G)vertical bar(3k)) for each fixed k >= 1 and are also applicable to the weighted case.

关键词： k-domination Total k-domination Proper interval graph polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Characterizing Star-PCGs 24th

Characterizing Star-PCGs

引用

24th International Computing and Combinatorics Conference (COCOON)

作者： Xiao, Mingyu Nagamochi, Hiroshi Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Sichuan Peoples R China Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto Japan

ISBN: (纸本)9783319947761;9783319947754

A graph G is called a pairwise compatibility graph (PCG, for short) if it admits a tuple (T, w, d(min), d(max)) of a tree T whose leaf set is equal to the vertex set of G, a non-negative edge weight w, and two non-negative reals d(min) <= d(max) such that G has an edge between two vertices u, v is an element of V if and only if the distance between the two leaves u and v in the weighted tree (T, w) is in the interval [d(min), d(max)]. The tree T is also called a witness tree of the PCG G. The problem of testing if a given graph is a PCG is not known to be NP -hard yet. To obtain a complete characterization of PCGs is a wide open problem in computational biology and graph theory. In the literature, most witness trees admitted by known PCGs are stars and caterpillars. In this paper, we give a complete characterization for a graph to be a star-PCG (a PCG that admits a star as its witness tree), which provides us the first polynomial-time algorithm for recognizing star-PCGs.

关键词： Pairwise compatibility graph polynomial-time algorithm Graph algorithm Graph theory

来源：评论

学校读者我要写书评

暂无评论

Two complexity results for the vertex coloring problem

引用

DISCRETE APPLIED MATHEMATICS 2017年 219卷 158-166页

作者： Malyshev, D. S. Lobanova, O. O. Natl Res Univ Higher Sch Econ 25-12 Bolshaya Pecherskaya Ulitsa Nizhnii Novgorod 603155 Russia Lobachevsky State Univ Nizhny Novgorod 23 Gagarina Ave Nizhnii Novgorod 603950 Russia

We. show that the chromatic number of {P-5, K-p - e}-free graphs can be computed in polynomial time for each fixed p. Additionally, we prove polynomial-time solvability of the weighted vertex coloring problem for (P-5... 详细信息

关键词： Computational complexity Coloring problem Hereditary class polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Global probability maximization for a Gaussian bilateral inequality in polynomial time

引用

JOURNAL OF GLOBAL OPTIMIZATION 2017年第4期68卷 879-898页

作者： Minoux, Michel Zorgati, Riadh UPMC LIP6 4 Pl Jussieu F-75252 Paris 05 France EDF Lab Paris Saclay R&D OSIRIS 7 Bd Gaspard Monge F-91120 Palaiseau France

The present paper investigates Gaussian bilateral inequalities in view of solving related probability maximization problems. Since the function f representing the probability of satisfaction of a given Gaussian bilateral inequality is not concave everywhere, we first state and prove a necessary and sufficient condition for negative semi-definiteness of the Hessian. Then, the (nonconvex) problem of globally maximizing f over a given polyhedron in Rn is adressed, and shown to be polynomial-time solvable, thus yielding a new-comer to the (short) list of nonconvex global optimization problems which can be solved exactly in polynomial time. Application to computing upper bounds to the maximum joint probability of satisfaction of a set of m independent Gaussian bilateral inequalities is discussed and computational results are reported.

关键词： Random gaussian inequalities Bilateral chance constraints Global optimization Joint probability maximization polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

WQO is decidable for factorial languages

引用

INFORMATION AND COMPUTATION 2017年 256卷 321-333页

作者： Atminas, Aistis Lozin, Vadim Moshkov, Mikhail London Sch Econ Dept Math Houghton St London WC2A 2AE England Univ Warwick Math Inst Coventry CV4 7AL W Midlands England KAUST CEMSE Div Thuwal 239556900 Saudi Arabia

A language is factorial if it is closed under taking factors, i.e. contiguous subwords. Every factorial language can be described by an antidictionary, i.e. a minimal set of forbidden factors. We show that the problem of deciding whether a factorial language given by a finite antidictionary is well-quasi-ordered under the factor containment relation can be solved in polynomial time. We also discuss possible ways to extend our solution to permutations and graphs. (C) 2017 Elsevier Inc. All rights reserved.

关键词： Well-quasi-ordering Factorial language polynomial-time algorithm Induced subgraph Permutation

来源：评论

学校读者我要写书评

暂无评论

More results on weighted independent domination

引用

THEORETICAL COMPUTER SCIENCE 2017年 700卷 63-74页

作者： Lozin, Vadim Malyshev, Dmitriy Mosca, Raffaele Zamaraev, Viktor Univ Warwick Math Inst Coventry CV4 7AL W Midlands England Natl Res Univ Higher Sch Econ 25-12 Bolshaya Pecherskaya Ulitsa Nizhnii Novgorod 603155 Russia Univ G DAnnunzio Dipartimento Econ I-65121 Pescara Italy

Weighted independent domination is an NP-hard graph problem, which remains computationally intractable in many restricted graph classes. In particular, the problem is NP-hard in the classes of sat-graphs and chordal graphs. We strengthen these results by showing that the problem is NP-hard in a proper subclass of the intersection of sat-graphs and chordal graphs. On the other hand, we identify two new classes of graphs where the problem admits polynomial-time solutions. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Independent domination polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

"Almost-stable" matchings in the Hospitals/Residents problem with Couples

引用

CONSTRAINTS 2017年第1期22卷 50-72页

作者： Manlove, David F. McBride, Iain Trimble, James Univ Glasgow Sch Comp Sci Sir Alwyn Williams Bldg Glasgow G12 8QQ Lanark Scotland

The Hospitals / Residents problem with Couples (hrc) models the allocation of intending junior doctors to hospitals where couples are allowed to submit joint preference lists over pairs of (typically geographically close) hospitals. It is known that a stable matching need not exist, so we consider min bp hrc, the problem of finding a matching that admits the minimum number of blocking pairs (i.e., is "as stable as possible"). We show that this problem is NP-hard and difficult to approximate even in the highly restricted case that each couple finds only one hospital pair acceptable. However if we further assume that the preference list of each single resident and hospital is of length at most 2, we give a polynomial-time algorithm for this case. We then present the first Integer Programming (IP) and Constraint Programming (CP) models for min bp hrc. Finally, we discuss an empirical evaluation of these models applied to randomly-generated instances of min bp hrc. We find that on average, the CP model is about 1.15 times faster than the IP model, and when presolving is applied to the CP model, it is on average 8.14 times faster. We further observe that the number of blocking pairs admitted by a solution is very small, i.e., usually at most 1, and never more than 2, for the (28,000) instances considered.

关键词： Most-stable matching Blocking pair polynomial-time algorithm NP-hardness Integer programming model Constraint programming model Empirical evaluation

来源：评论

学校读者我要写书评

暂无评论

Reconstructing Phylogenetic Level-1 Networks from Nondense Binet and Trinet Sets

引用

algorithmICA 2017年第1期77卷 173-200页

作者： Huber, Katharina T. van Iersel, Leo Moulton, Vincent Scornavacca, Celine Wu, Taoyang Univ East Anglia Sch Comp Sci Norwich Norfolk England Delft Univ Technol Delft Inst Appl Math Delft Netherlands Univ Montpellier CNRS ISEM Montpellier France Inst Biol Computat Montpellier France

Binets and trinets are phylogenetic networks with two and three leaves, respectively. Here we consider the problem of deciding if there exists a binary level-1 phylogenetic network displaying a given set T of binary binets or trinets over a taxon set X, and constructing such a network whenever it exists. We show that this is NP-hard for trinets but polynomial-time solvable for binets. Moreover, we show that the problem is still polynomial-time solvable for inputs consisting of binets and trinets as long as the cycles in the trinets have size three. Finally, we present an O(3(vertical bar X vertical bar) poly(vertical bar X vertical bar)) time algorithm for general sets of binets and trinets. The latter two algorithms generalise to instances containing level-1 networks with arbitrarily many leaves, and thus provide some of the first supernetwork algorithms for computing networks from a set of rooted phylogenetic networks.

关键词： Phylogenetic tree Phylogenetic network polynomial-time algorithm Exponential-time algorithm NP-hard Supernetwork Trinet Aho algorithm

来源：评论

学校读者我要写书评

暂无评论

Multiple objective solution approaches for aircraft rerouting under the disruption of multi-aircraft

引用

EXPERT SYSTEMS WITH APPLICATIONS 2017年 83卷 283-299页

作者： Hu, Yuzhen Liao, Hong Zhang, Song Song, Yan Harbin Engn Univ Sch Econ & Management Harbin 150001 Heilongjiang Peoples R China

This paper considers a multi-objective aircraft recovery problem for airline disruption. An integer programming formulation is first established based on connection network with three conflicting objectives, where the first objective minimizes the total deviation from original flight schedules, the second objective minimizes the maximal flight delay time, and the third objective minimizes the number of aircraft actually attended in swapping. Optimal analysis is provided for a small scale aircraft recovery problem with the last two objectives and then one polynomial time algorithm for aircraft recovery problem after the disruption to multi-aircraft in a fleet at an airport. One heuristic combined epsilon-constraints method and neighborhood search algorithm is designed for large scale disruption recovery problem. The results obtained from computational experiment illustrate effectiveness and efficiency of the heuristic. The outcome of this research could provide theoretical and practical supports for airlines to reduce flight delays. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Aircraft rerouting Multiple objective polynomial-time algorithm epsilon-constraints method Neighborhood search algorithm

来源：评论

学校读者我要写书评

暂无评论

3-colouring for dually chordal graphs and generalisations

引用

INFORMATION PROCESSING LETTERS 2017年第Dec.期128卷 21-26页

作者： Leitert, Arne Kent State Univ Dept Comp Sci Kent OH 44240 USA

In this paper, we investigate the Colourability problem for dually chordal graphs and some of its generalisations. We show that the problem remains NP-complete if limited to four colours. For the case of three colours, we present a simple linear time algorithm for dismantlable graphs (which include dually chordal graphs) and present an O(n(3)m) time algorithm for graphs with tree-breadth 1. Additionally, we show that a dually chordal graph is 3-colourable if and only if it is perfect and has no clique of size four. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Dually chordal graphs Tree-breadth 3-colourability Graph algorithms polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：