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

On a weighted linear matroid intersection algorithm by Deg-Det computation

JAPAN JOURNAL OF INDUSTRIAL AND APPLIED MATHEMATICS 2020年第3期37卷 677-696页

作者： Furue, Hiroki Hirai, Hiroshi Univ Tokyo Grad Sch Informat Sci & Technol Dept Math Informat Tokyo 1138656 Japan

In this paper, we address the weighted linear matroid intersection problem from computation of the degree of the determinant of a symbolic matrix. We show that a generic algorithm computing the degree of noncommutative determinants, proposed by the second author, becomes an O(mn(3) log n) time algorithm for the weighted linear matroid intersection problem, where two matroids are given by column vectors of n x m matrices A, B. We reveal that our algorithm is viewed as a "nonstandard" implementation of Frank's weight splitting algorithm for linear matroids. This gives a linear algebraic reasoning to Frank's algorithm. Although our algorithm is slower than existing algorithms in the worst case estimate, it has a notable feature. Contrary to existing algorithms, our algorithm works on different matroids represented by another "sparse" matrices A(0), B-0, which skips unnecessary Gaussian eliminations for constructing residual graphs.

关键词： Combinatorial optimization polynomial time algorithm Weighted matroid intersection The degree of determinant Weight splitting

来源：评论

学校读者我要写书评

暂无评论

Permutation flow shop scheduling with dominant machines to minimize discounted total weighted completion time

引用

APPLIED MATHEMATICS AND COMPUTATION 2006年第1期182卷 947-954页

作者： Wang, Ji-Bo Shan, Feng Jiang, Bo Wang, Li-Yan Shenyang Inst Aeronaut Engn Dept Sci Shenyang 110034 Peoples R China

This paper deals with some special cases of general, no-wait and no-idle permutation flow shop scheduling problems, respectively. Special cases means that the machines form an increasing series of dominant machines, a decreasing series of dominant machines, an increasing-decreasing series of dominant machines and a decreasing-increasing series of dominant machines. Efficient polynomial time algorithms for finding the optimal schedules to minimize discounted total weighted completion time are developed. (c) 2006 Elsevier Inc. All rights reserved.

关键词： scheduling flow shop discounted total weighed completion time polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Secure communication design for multi-user peer-to-peer wireless relay networks

引用

IET COMMUNICATIONS 2016年第7期10卷 770-777页

作者： Gong, Xiangwu Long, Hang Dong, Feihong Yin, Hao PLA Univ Sci & Technol Coll Commun Engn Nanjing Jiangsu Peoples R China PLAAF Unit 95899 Beijing 100000 Peoples R China Beijing Univ Posts & Telecommun Beijing 100876 Peoples R China Inst China Elect Syst Engn Corp Beijing 100141 Peoples R China

In this study, physical layer security techniques are studied for multi-user peer-to-peer relay networks using amplify-and-forward protocol in the presence of an eavesdropper. Two system designs are considered: the minimum achievable secrecy rate maximisation and the total transmit power minimisation. First, considering user fairness, the authors study the max-min achievable secrecy rate problem subject to a total transmit power constraint. Mathematically, the optimisation problem is non-linear and non-convex. They propose a polynomial time algorithm based on the bisection technique to solve it. Second, they study the total transmit power minimisation problem which aims at minimising the total transmit power at relays such that individual secrecy rate for each user is satisfied. The total power optimisation problem is also non-convex, so they use the relaxation technique to transform it into a convex problem which can be efficiently solved by the gradient-based algorithms. Numerical evaluation of the obtained secrecy rate and transmit power results shows that the proposed designs can significantly improve the performance of secure wireless communications.

关键词： relay networks (telecommunication) radio networks peer-to-peer computing amplify and forward communication protocols minimisation minimax techniques nonlinear programming concave programming polynomials relaxation theory convex programming gradient methods computer network security secure wireless communication design multiuser peer-to-peer wireless relay network physical layer security technique amplify-and-forward protocol secrecy rate maximisation max-min achievable secrecy rate problem nonlinear optimisation problem nonconvex optimisation problem mathematical analysis polynomial time algorithm power minimisation problem total power optimisation problem relaxation technique convex problem gradient-based algorithm numerical evaluation

来源：评论

学校读者我要写书评

暂无评论

algorithmic results on double Roman domination in graphs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2020年第1期39卷 90-114页

作者： Banerjee, S. Henning, Michael A. Pradhan, D. Indian Inst Technol ISM Dhanbad Bihar India Univ Johannesburg Math Pure & Appl Math ZA-2006 Auckland Pk South Africa

Given a graph G = (V, E), a function f : V -> {0, 1, 2, 3} is called a double Roman dominating function on G if (i) for every v. V with f (v) = 0, there are at least two neighbors of v that are assigned 2 under f or at least a neighbor of v that is assigned 3 under f, and (ii) for every vertex v with f (v) = 1, there is at least one neighbor w of v with f (w) >= 2. The weight of a double Roman dominating function f is f (V) = Sigma(u is an element of V) f (u). The double Roman domination number of G, denoted by gamma(dR)(G) is the minimum weight of a double Roman dominating function on G. For a graph G = (V, E), MIN-DOUBLE-RDF is to find a double Roman dominating function f with f (V) = gamma(dR)(G). The decision version of MIN-DOUBLE-RDF is shown to be NP-complete for chordal graphs and bipartite graphs. In this paper, we first strengthen the known NP-completeness of the decision version of MIN-DOUBLE-RDF by showing that the decision version of MIN-DOUBLE-RDF remains NP-complete for undirected path graphs, chordal bipartite graphs, and circle graphs. We then present linear time algorithms for computing the double Roman domination number in proper interval graphs and block graphs. We then discuss on the approximability of MIN-DOUBLE-RDF and present a 2-approximation algorithm in 3-regular bipartite graphs.

关键词： Domination Roman domination Double Roman domination polynomial time algorithm NP-complete

来源：评论

学校读者我要写书评

暂无评论

Matrix partitions of perfect graphs

引用

DISCRETE MATHEMATICS 2006年第19-20期306卷 2450-2460页

作者： Feder, Tomas Hell, Pavol Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada

Given a symmetric m by m matrix M over 0, 1, *, the M-partition problem asks whether or not an input graph G can be partitioned into m parts corresponding to the rows (and columns) of M so that two distinct vertices from parts i and j (possibly with i = j) are non-adjacent if M(i, j) = 0, and adjacent if M(i, j) = 1. These matrix partition problems generalize graph colourings and homomorphisms, and arise frequently in the study of perfect graphs;example problems include split graphs, clique and skew cutsets, homogeneous sets, and joins. In this paper we study M-partitions restricted to perfect graphs. We identify a natural class of 'normal' matrices M for which M-partitionability of perfect graphs can be characterized by a finite family of forbidden induced subgraphs (and hence admits polynomial time algorithms for perfect graphs). We further classify normal matrices into two classes: for the first class, the size of the forbidden subgraphs is linear in the size of M;for the second class we only prove exponential bounds on the size of forbidden subgraphs. (We exhibit normal matrices of the second class for which linear bounds do not hold.) We present evidence that matrices M which are not normal yield badly behaved M-partition problems: there are polynomial time solvable M-partition problems that do not have finite forbidden subgraph characterizations for perfect graphs. There are M-partition problems that are NP-complete for perfect graphs. There are classes of matrices M for which even proving 'dichotomy' of the corresponding M-partition problems for perfect graphs-i.e., proving that these problems are all polynomial or NP-complete-is likely to be difficult. (c) 2006 Elsevier B.V. All rights reserved.

关键词： perfect graph matrix partition M-partition trigraph homomorphism forbidden subgraph characterization polynomial time algorithm NP-complete problem

来源：评论

学校读者我要写书评

暂无评论

An Efficient Pattern Matching algorithm for Unordered Term Tree Patterns of Bounded Dimension

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2018年第9期E101A卷 1344-1354页

作者： Shoudai, Takayoshi Miyahara, Tetsuhiro Uchida, Tomoyuki Matsumoto, Satoshi Suzuki, Yusuke Kyushu Int Univ Fac Contemporary Business Kitakyushu Fukuoka 8058512 Japan Hiroshima City Univ Fac Informat Sci Hiroshima 7313194 Japan Tokai Univ Fac Sci Hiratsuka Kanagawa 2591292 Japan

A term tree pattern is a connected acyclic graph (unrooted unordered tree) pattern with structured variables, which are ordered lists of one or more distinct vertices. A variable of a termtree pattern has a variable label and can be replaced with an arbitrary tree by hyperedge replacement according to the variable label. The dimension of a term tree pattern is the maximum number of vertices in the variables of it. A term tree pattern is said to be linear if each variable label in it occurs exactly once. Let T be a tree and t a linear termtree pattern. In this paper, we study the graph pattern matching problem (GPMP) for T and t, which decides whether or not T is obtained from t by replacing variables in t with some trees. First we show that GPMP for T and t is NP-complete if the dimension of t is greater than or equal to 4. Next we give a polynomial time algorithm for solving GPMP for a tree of bounded degree and a linear term tree pattern of bounded dimension. Finally we show that GPMP for a tree of arbitrary degree and a linear term tree pattern of dimension 2 is solvable in polynomial time.

关键词： tree structured pattern graph pattern matching algorithm polynomial time algorithm NP-completeness

来源：评论

学校读者我要写书评

暂无评论

algorithm and hardness results on hop domination in graphs

引用

INFORMATION PROCESSING LETTERS 2020年 153卷 105872-000页

作者： Henning, Michael A. Pal, Saikat Pradhan, D. Univ Johannesburg Math Pure & Appl Math ZA-2006 Auckland Pk South Africa Indian Inst Technol ISM Dept Math & Comp Dhanbad Bihar India

Two vertices in a graph are said to 2-step dominate each other if they are at distance 2 apart. A set S of vertices in a graph G = (V, E) is a hop dominating set of G if every vertex outside S is 2-step dominated by some vertex of S. Given a graph G, MIN-HDS is the problem of finding a hop dominating set of G of minimum cardinality. The decision version of MIN-HDS is known to be NP-complete for planar bipartite graphs and planar chordal graphs, and hence for bipartite graphs and chordal graphs. In this paper, we present a linear time algorithm for computing a minimum hop dominating set in bipartite permutation graphs, which is a subclass of bipartite graphs. We also show that MIN-HDS cannot be approximated within a factor of (1 - epsilon) In vertical bar V vertical bar, unless P=NP and can be approximated within a factor of 1 + In(Delta(Delta - 1) + 1), where Delta denotes the maximum degree in the graph G. Finally, we show that MIN-HDS is APX-complete for bipartite graphs of maximum degree 3. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Domination Hop domination polynomial time algorithm NP-complete Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Perfect Italian domination in graphs: Complexity and algorithms

引用

DISCRETE APPLIED MATHEMATICS 2022年 319卷 271-295页

作者： Pradhan, D. Banerjee, S. Liu, Jia-Bao Indian Inst Technol ISM Dhanbad Dept Math & Comp Dhanbad Bihar India Anhui Jianzhu Univ Sch Math & Phys Hefei 230601 Peoples R China

An Italian dominating function on a simple undirected graph G is a function f : V(G) -> {0, 1, 2} satisfying the condition that for each vertex v with f (v) = 0, Sigma(u epsilon NG(v)) f(u) >= 2. An Italian dominating function f on G is called a perfect Italian dominating function on G if for each vertex v with f (v) = 0, Sigma(u epsilon NG(v)) f (u) = 2. The weight of a function f on a graph G, denoted by w(f), is the sum Sigma(u epsilon V(G)) f (v). For a simple undirected graph G, Min-PIDF is the problem of finding the minimum weight of a perfect Italian dominating function on G. First, we discuss the complexity difference between Min-PIDF and the problem of finding the minimum weight of an Italian dominating function. We then establish the NP-completeness of the decision version of Min-PIDF in chordal graphs and investigate the hardness of approximation of Min-PIDF in general graphs. Finally, we present linear time algorithms for computing the minimum weight of a perfect Italian dominating function in block graphs and series-parallel graphs. (c) 2021 Elsevier B.V. All rights reserved.

关键词： Domination Italian domination Perfect Italian domination polynomial time algorithm NP-complete

来源：评论

学校读者我要写书评

暂无评论

Capacity acquisition for the single-item lot sizing problem under energy constraints

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2018年 81卷 112-122页

作者： Rapine, Christophe Penz, Bernard Gicquel, Celine Akbalik, Ayse Univ Lorraine LGIPM Technopole Metz F-57070 Metz France Univ Grenoble Alpes G SCOP Grenoble INP CNRS F-38000 Grenoble France Univ Paris Saclay LRI Univ Paris Sud F-91405 Orsay France

We study a single-item lot sizing problem integrated with some energy constraints, called energy-LSP in the rest of the paper. We consider a production system composed of identical and capacitated machines in parallel. One has to decide how many machines to start and how much to produce to serve the demand and/or to replenish the inventory. In addition to the production capacity limit in each period, induced by the machines on, we have a limit on the energy that can be consumed by the start-ups of the machines and the production of units. We first provide a mixed integer programming formulation for the problem in the general case. We then develop efficient polynomial time algorithms running in 0(Tlog T), with T the length of the planning horizon, for several subproblems: (i) energy-LSP where all energy parameters are set to 0, (ii) energy-LSP where only the machine start-ups consume energy, (iii) energy-LSP where only the production of units consumes energy. We show that, in all these special cases, energy-LSP can be seen as an extension of the integrated capacity acquisition and lot sizing problem. This allows us, as by-product of our approach, to significantly improve the existing result proposed for the capacity acquisition problem without energy constraint nor subcontracting. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Energy efficient manufacturing Lot sizing Capacity acquisition Energy constraints polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

algorithms for the partial inverse matroid problem in which weights can only be increased

引用

JOURNAL OF GLOBAL OPTIMIZATION 2016年第4期65卷 801-811页

作者： Zhang, Zhao Li, Shuangshuang Lai, Hong-Jian Du, Ding-Zhu Zhejiang Normal Univ Coll Math Phys & Informat Engn Jinhua 321004 Zhejiang Peoples R China Xinjiang Univ Coll Math & Syst Sci Urumqi 830046 Xinjiang Peoples R China West Virginia Univ Dept Math Morgantown WV 26506 USA Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

In a partial inverse combinatorial problem, given a partial solution, the goal is to modify data as small as possible such that there exists an optimal solution containing the given partial solution. In this paper, we study a constraint version of the partial inverse matroid problem in which the weight can only be increased. Two polynomial time algorithms are presented for this problem.

关键词： Partial inverse optimization problem Matroid Weight constraint polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：