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

NETWORKS 1998年第4期32卷 233-253页

作者： Hall, NG Liu, WP Sidney, JB Univ Ottawa Fac Adm Ottawa ON K1N 6N5 Canada Ohio State Univ Columbus OH 43210 USA

Broadcasting in a communications network has been the subject of many studies in recent years. The studies vary in their assumptions governing the behavior of the network and in their objectives with respect to the network. Almost all the work to date uses the unit transmission time assumption, that is, the message transmission times between all pairs of vertices are equal. In this paper, we investigated the broadcast problem under four more general transmission time assumptions. In addition, four different objective functions were considered, including the minimization of (1) the broadcast time (the maximum time for any vertex to receive the message), (2) the average time to receive the message (both with and without ready times at the vertices), (3) the weighted average time to receive the message, and (4) the cycle time. Of the 20 problems thus generated, four admit polynomial time algorithms, 15 are (in the equivalent recognition version) unary NP-complete, and the complexity status of one remains open. All these results are proved, and heuristics with an attainable constant worst-case performance ratio are provided for two of the problems for which polynomial time algorithms are not found. (C) 1998 John Wiley & Sons, Inc.

关键词： broadcasting scheduling polynomial time algorithm NP-complete

来源：评论

学校读者我要写书评

暂无评论

C-graph automatic groups

引用

JOURNAL OF ALGEBRA 2014年 413卷 289-319页

作者： Elder, Murray Taback, Jennifer Univ Newcastle Sch Math & Phys Sci Callaghan NSW 2308 Australia Bowdoin Coll Dept Math Brunswick ME 04011 USA

We generalize the notion of a graph automatic group introduced by Kharlampovich, Khoussainov and Miasnikov by replacing the regular languages in their definition with more powerful language classes. For a fixed language class C, we call the resulting groups C-graph automatic. We prove that the class of C-graph automatic groups is closed under change of generating set, direct and free product for certain classes C. We show that for quasi-realtime counter-graph automatic groups where normal forms have length that is linear in the geodesic length, there is an algorithm to compute normal forms (and therefore solve the word problem) in polynomial time. The class of quasi-realtime counter-graph automatic groups includes all Baumslag-Solitar groups, and the free group of countably infinite rank. Context-sensitive-graph automatic groups are shown to be a very large class, which encompasses, for example, groups with unsolvable conjugacy problem, the Grigorchuk group, and Thompson's groups F,T and V. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Automatic group Cayley graph automatic group Counter language Context-sensitive language Word problem polynomial time algorithm Baumslag-Solitar group

来源：评论

学校读者我要写书评

暂无评论

Roll cutting in the curtain industry, or: A well-solvable allocation problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2007年第3期183卷 1397-1404页

作者： Alfieri, Arianna van de Velde, Steef Woeginger, Gerhard J. Erasmus Univ RSM NL-3000 DR Rotterdam Netherlands Politecn Torino Dipartimento Sistemi Prod & Econ Azienda I-10129 Turin Italy Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 MB Eindhoven Netherlands

We study the problem of cutting a number of pieces of the same length from n rolls of different lengths so that the remaining part of each utilized roll is either sufficiently short or sufficiently long. A piece is 'sufficiently short', if it is shorter than a pre-specified threshold value delta(min), so that it can be thrown away as it cannot be used again for cutting future orders. And a piece is 'sufficiently long', if it is longer than a pre-specified threshold value delta(max), (with delta(max) > delta(min)), so that it can reasonably be expected to be usable for cutting future orders of almost any length. We show that this problem, faced by a curtaining wholesaler, is solvable in O(nlogn) time by analyzing a non-trivial class of allocation problems. (c) 2006 Elsevier B.V. All rights reserved.

关键词： cutting allocation problem polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

DECIDING POSITIVITY OF LITTLEWOOD-RICHARDSON COEFFICIENTS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2013年第4期27卷 1639-1681页

作者： Buergisser, Peter Ikenmeyer, Christian Univ Paderborn Inst Math D-33098 Paderborn Germany

Starting with Knutson and Tao's hive model [J. Amer. Math. Soc., 12 (1999), pp. 1055-1090] we characterize the Littlewood-Richardson coefficient c(lambda)(nu),(mu) of given partitions lambda, mu, nu is an element of N-n as the number of capacity achieving hive flows on the honeycomb graph. Based on this, we design a polynomial time algorithm for deciding c(lambda)(nu),(mu) > 0. This algorithm is easy to state and takes O(n(3) log nu(1)) arithmetic operations and comparisons. We further show that the capacity achieving hive flows can be seen as the vertices of a connected graph, which leads to new structural insights into Littlewood-Richardson coefficients.

关键词： Littlewood-Richardson coefficients hive model polynomial time algorithm flows in networks

来源：评论

学校读者我要写书评

暂无评论

NEW GEOMETRIC REPRESENTATIONS AND DOMINATION PROBLEMS ON TOLERANCE AND MULTITOLERANCE GRAPHS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2016年第3期30卷 1685-1725页

作者： Giannopoulou, Archontia C. Mertzios, George B. Tech Univ Berlin Inst Software Technol & Theoret Comp Sci D-10623 Berlin Germany Univ Durham Sch Engn & Comp Sci Durham DH1 County Durham England

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain amount of overlap without being in conflict. In one of the most natural generalizations of tolerance graphs with direct applications in the comparison of DNA sequences from different organisms, namely multitolerance graphs, two tolerances are allowed for each interval: one on the left side and the other on the right side. Several efficient algorithms for optimization problems that are NP-hard in general graphs have been designed for tolerance and multitolerance graphs. In spite of this progress, the complexity status of some fundamental algorithmic problems on tolerance and multitolerance graphs, such as the dominating set problem, remained unresolved until now-three decades after the introduction of tolerance graphs. In this paper we introduce two new geometric representations for tolerance and multitolerance graphs, given by points and line segments in the plane. Apart from being important on their own, these new representations prove to be a powerful tool for deriving both hardness results and polynomial time algorithms. Using them, we surprisingly prove that the dominating set problem can be solved in polynomial time on tolerance graphs and that it is APX-hard on multitolerance graphs, thus solving a longstanding open problem. This problem is the first one that has been discovered with a different complexity status in these two graph classes.

关键词： tolerance graph multitolerance graph geometric representation dominating set problem polynomial time algorithm APX-hard

来源：评论

学校读者我要写书评

暂无评论

A class of inverse dominant problems under weighted l_∞ norm and an improved complexity bound for Radzik's algorithm

引用

JOURNAL OF GLOBAL OPTIMIZATION 2006年第4期34卷 551-567页

作者： Wang, Q Yang, XG Zhang, JZ China Jiliang Univ Dept Math Hangzhou 310018 Peoples R China Chinese Acad Sci Inst Syst Sci Beijing 100080 Peoples R China City Univ Hong Kong Dept Math Hong Kong Hong Kong Peoples R China

In this paper, we first discuss a class of inverse dominant problems under weighted l(infinity) norm, which is how to change the original weights of elements with bounds in a finite ground set so that a given set becomes a weakly dominant set with respect to a given collection of subsets under the new weights and the largest change of the weights is minimum. This model includes a large class of improvement problems in combinatorial optimization. We propose a Newton-type algorithm for the model. This algorithm can solve the model in strongly polynomial time if the subproblem involved is solvable in strongly polynomial time. In the second part of the paper, we improve the complexity bound for Radzik's Newton-type method which is designed to solve linear fractional combinatorial optimization problems. As Radzik's method is closely related to our algorithm, this bound also estimates the complexity of our algorithm.

关键词： dominant set improvement problem inverse problem linear fractional combinatorial optimization polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Production Scheduling with History-Dependent Setup times

引用

NAVAL RESEARCH LOGISTICS 2012年第1期59卷 58-68页

作者： Lee, Kangbok Lei, Lei Pinedo, Michael Rutgers State Univ Rutgers Business Sch Dept Supply Chain Management & Mkt Sci Newark NJ 07102 USA NYU Stern Sch Business Dept Informat Operat & Management Sci New York NY USA

We consider a parallel-machine scheduling problem with jobs that require setups. The duration of a setup does not depend only on the job just completed but on a number of preceding jobs. These setup times are referred to as history-dependent. Such a scheduling problem is often encountered in the food processing industry as well as in other process industries. In our model, we consider two types of setup times-a regular setup time and a major setup time that becomes necessary after several "hard-to-clean" jobs have been processed on the same machine. We consider multiple objectives, including facility utilization, flexibility, number of major setups, and tardiness. We solve several special cases assuming predetermined job sequences and propose strongly polynomial time algorithms to determine the optimal timing of the major setups for given job sequences. We also extend our analysis to develop pseudopolynomial time algorithms for cases with additional objectives, including the total weighted completion time, the total weighted tardiness, and the weighted number of tardy jobs. (C) 2012 Wiley Periodicals, Inc. Naval Research Logistics 59: 58-68, 2012

关键词： history-dependent setup times parallel-machine scheduling fixed job sequences polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

On the complexity of the identifiable subgraph problem, revisited

引用

DISCRETE APPLIED MATHEMATICS 2017年 226卷 78-86页

作者： Kratsch, Stefan Milanic, Martin Univ Bonn Inst Comp Sci Friedrich Ebert Allee 144 D-53113 Bonn Germany Univ Primorska UP IAM Muzejski Trg 2 SI-6000 Koper Slovenia Univ Primorska UP FAMNIT Glagoljaska 8 SI-6000 Koper Slovenia

A bipartite graph G = (L, R;E) with at least one edge is said to be identifiable if for every vertex v is an element of L, the subgraph induced by its non-neighbors has a matching of cardinality |L| - 1. An l-subgraph of G is an induced subgraph of G obtained by deleting from it some vertices in L together with all their neighbors. The IDENTIFIABLE SUBGRAPH problem is the problem of determining whether a given bipartite graph contains an identifiable l-subgraph. The MIN- and MAX-IDENTIFIABLE SUBGRAPH problems are defined similarly, taking into account a given upper, resp. lower bound on the number of vertices from L in an identifiable l-subgraph. We show that the IDENTIFIABLE SUBGRAPH and MAX-IDENTIFIABLE SUBGRAPH problems are polynomially solvable, thereby answering the question about the complexity of these two problems posed by Fritzilas et al. in 2013. We also complement a known APX-hardness result for the MIN-IDENTIFIABLE SUBGRAPH problem by showing that two parameterized variants of the problem are W[1]-hard. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Bipartite graph Matching Identifiable graph Computational complexity polynomial time algorithm W-hardness

来源：评论

学校读者我要写书评

暂无评论

The k-th Roman domination problem is polynomial on interval graphs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2024年第3期48卷 1-14页

作者： Li, Peng Chongqing Univ Technol 69 Hongguang Rd Chongqing Peoples R China

Let G be some simple graph and k be any positive integer. Take h : V ( G )- {0,1, , ... ,k+1} and v is an element of V (G), let AN(h)(v) denote the set of vertices w is an element of N-G (v) with h (w) >= 1. Let AN(h)[v] h [v] = AN(h)(v) boolean OR {v}. The function h is a [k]-Roman dominating function of G if h ( AN(h)[v]) >= |AN(h)(v)|+ k holds for any v is an element of V(G). The minimum weight of such a function is called the k-th Roman Domination number of G, which is denoted by gamma(kR) (G). In 2020, Banerjee et al. presented linear time algorithms to compute the double Roman domination number on proper interval graphs and block graphs. They posed the open question that whether there is some polynomial time algorithm to solve the double Roman domination problem on interval graphs. It is argued that the interval graph is a nontrivial graph class. In this article, we design a simple dynamic polynomial time algorithm to solve the k-th Roman domination problem on interval graphs for each fixed integer k > 1.

关键词： Domination Roman domination k-th Roman domination polynomial time algorithm Interval graphs

来源：评论

学校读者我要写书评

暂无评论

algorithm and hardness results on neighborhood total domination in graphs

引用

THEORETICAL COMPUTER SCIENCE 2020年 840卷 16-32页

作者： Jha, Anupriya Pradhan, D. Banerjee, S. Indian Inst Technol ISM Dhanbad Dept Math & Comp Dhanbad Bihar India

A set D subset of V of a graph G = (V, E) is called a neighborhood total dominating set of G if D is a dominating set and the subgraph of G induced by the open neighborhood of D has no isolated vertex. Given a graph G, MIN-NTDS is the problem of finding a neighborhood total dominating set of G of minimum cardinality. The decision version of MIN-NTDS is known to be NP-complete for bipartite graphs and chordal graphs. In this paper, we extend this NP-completeness result to undirected path graphs, chordal bipartite graphs, and planar graphs. We also present a linear time algorithm for computing a minimum neighborhood total dominating set in proper interval graphs. We show that for a given graph G = (V, E), MIN-NTDS cannot be approximated within a factor of (1 - epsilon) log vertical bar V vertical bar, unless NP subset of Dtime(vertical bar V vertical bar(O(loglog vertical bar V vertical bar))) and can be approximated within a factor of O(log Delta), where Delta is the maximum degree of the graph G. Finally, we show that MIN-NTDS is APX-complete for graphs of degree at most 3. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Domination Total domination Neighborhood total domination polynomial time algorithm NP-complete APX-complete

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：