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

International Conference on Computers and Industrial Engineering (CIE39)

作者： Kats, Vladimir Levner, Eugene Inst Ind Math Beer Sheva Israel Holon & Bar Dan Univ Holon Inst Technol Ramat Gan Israel

ISBN: (纸本)9781424441358

We consider the original routing algorithm invented by Romanovskii (1967) for solving a cyclic project scheduling problem and establish its close relationship with the well-known routing algorithm by Dantzig, Blattner and Rao (1967). Though Romanovskii's and Dantzig-Blattner-Rao's algorithms can only treat fixed numerical data, we show that they both can be extended to solve problems with interval-valued input data.

关键词： Scheduling routing algorithm robotic scheduling polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Max-Plus Matrix Method for Correctness Verification of Communication Protocols 15th

Max-Plus Matrix Method for Correctness Verification of Commu...

引用

15th IFAC Workshop on Discrete Event Systems (WODES)

作者： Wang, Cailu Tao, Yuegang Tan, Jianguo Beijing Inst Technol Sch Automat Beijing 100081 Peoples R China Hebei Univ Technol Sch Artificial Intelligence Tianjin 300130 Peoples R China Handan Inst Environm Protect Handan 056001 Peoples R China

Accompanied with the mushroom growth of communication technology, the correct operation of protocols has been widely concerned and studied in the field of communication. The correctness verification is a difficult problem due to the state space explosion. In this paper, the event graph model of a communication protocol is established and verification matrix is proposed to verify the correctness of the protocol. It is found out that the correctness of a protocol is equivalent to the nilpotency of the verification matrix on the max-plus algebra framework. The matrix method is constructive and leads to a polynomial algorithm for verifying the correctness of protocols. Some examples about stop-and-wait protocols and handshake protocols are taken to illustrate how the presented results work in practical applications. Copyright (C) 2020 The Authors.

关键词： Communication protocol correctness verification event graph max-plus algebra verification matrix nilpotency polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree

An approximation for finding a smallest 2-edge-connected sub...

引用

5th Annual International Computing and Combinatorics Conference

作者： Nagamochi, H Toyohashi Univ Technol Dept Informat & Comp Sci Tempa Ku Toyohashi Aichi 418580 Japan

Given a graph G = (V, E) and a tree T = (V, F) with E boolean AND F = phi such that G + T = (V, F boolean OR E) is 2-edge-connected, we consider the problem of finding a smallest 2-edge-connected spanning subgraph (V,F boolean OR E') of G + T containing T. The problem, which is known to be NP-hard, admits a 2-approximation algorithm. However, obtaining a factor better than 2 for this problem has been one of the main open problems in the graph augmentation problem. In this paper, we show that the problem is (1.875 + epsilon)-approximable in O(n(1/2)m+n(2)) time for any constant epsilon > 0, where n = \V\ and m = \E boolean OR F\. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： approximation algorithm edge-connectivity tree graphs spanning subgraph graph augmentation 2-edge-connectivity polynomial algorithm matching

来源：评论

学校读者我要写书评

暂无评论

Sensor Networks for Structural Health Monitoring of Critical Infrastructures Using Identifying Codes 15

Sensor Networks for Structural Health Monitoring of Critical...

引用

15th International Conference on the Design of Reliable Communication Networks (DRCN)

作者： Basu, Kaustav Dey, Sanjana Nandy, Subhas Sen, Arunabha Arizona State Univ NetXT Lab Tempe AZ 85287 USA Indian Stat Inst Kolkata India

ISBN: (纸本)9781538684610

The Structural Health Monitoring (SHM) problem for critical infrastructures using wireless sensor networks (WSN), has received considerable attention in the research community in recent years. Sensors placed in these infrastructures have two functions, sensing/coverage and communication. The thrust of this paper is on the coverage aspects of sensor networks. In the Point Coverage model, only a specified set of points in the deployment area have to be sensed. The goal of placement optimization is to find the smallest set of locations to deploy sensors, so that all the points of interest can be sensed. This problem often is solved by formulating it as a Set Cover problem. However, the Set Cover approach has a serious limitation on the accurate identification of the location where abnormality is sensed. In this paper, we present a technique to overcome this limitation by utilizing Identifying Code. We study two different scenarios, where the sensors and points of interest are located in one and two-dimensional spaces respectively. We provide a polynomial time optimal algorithm for the one-dimensional case and an Integer Linear Programming (ILP) based optimal solution for the two-dimensional case. We evaluate the efficacy of the ILP solution with varying network size (45 to 64655 nodes). The ILP produced an optimal solution for the largest instance with 64655 nodes and 155339 edges in only 180.45 seconds.

关键词： Structural Health Monitoring Identifying Code Discriminating Code Interval Bigraph polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

An algorithm for node-to-set disjoint paths problem in burnt pancake graphs

An algorithm for node-to-set disjoint paths problem in burnt...

引用

9th Pacific Rim International Symposium on Dependable Computing

作者： Kaneko, K Tokyo Univ Agr & Technol Fac Technol Koganei Tokyo 1848588 Japan

A burnt pancake graph is a variant of Cayley graphs and its topology is suitable for massively parallel systems. However, for a burnt pancake graph, there is much room for further research. Hence, in this study, we focus on n-burnt pancake graphs and propose an algorithm to obtain n disjoint paths from a source node to n destination nodes in polynomial order time of n, n being the degree of the graph. In addition, we estimate the time complexity of the algorithm and the sum of path lengths. We also give a proof of correctness of the algorithm. Moreover, we report the results of computer simulation to evaluate the average performance of the algorithm.

关键词： burnt pancake graph disjoint paths polynomial algorithm fault tolerance routing algorithm

来源：评论

学校读者我要写书评

暂无评论

Bichromatic triangle games

引用

Electronic Notes in Discrete Mathematics 2011年第C期37卷 105-110页

作者： Manić, Gordana Martin, Daniel M. Stojakoviš, Miloć Centro de Matemática Computação e Cognição Universidade Federal do ABC São Paulo Brazil Department of Mathematics and Informatics University of Novi Sad Serbia

We study a combinatorial game called Bichromatic Triangle Game, defined as follows. Two players R and B construct a triangulation on a given planar point set V. Starting from no edges, players R and B take turns drawing one edge that connects two points in V. Player R uses color red and player B uses color blue. The first player who completes one empty monochromatic triangle is the winner. We show that either player can force a tie in the Bichromatic Triangle Game when the points of V are in convex position and also in the case when there is exactly one inner point in the set V. As an easy consequence of those results, we obtain that the outcome of the Bichromatic Complete Triangulation Game (a version of the Bichromatic Triangle Game in which players draw edges until they complete a triangulation) is also a tie for the same two cases regarding set V. © 2011 Elsevier B.V.

关键词： Bichromatic triangle game Combinatorial games on graphs Games on triangulations polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Classification Problems for MDPs and Optimal Customer Admission to M/M/k/N Queues

Classification Problems for MDPs and Optimal Customer Admiss...

引用

作者： Fenghsu Yang Stony Brook University

学位级别：博士

My dissertation addresses the unichain classification problem for any finite Markov decision process (MDP) with a recurrent or stop- ping state and the optimal admission problem for an M/M/k/N queue with holding costs. In the first chapter, we study the unichain classification problem for MDPs. The unichain classification prob- lem is to detect whether an MDP with finite states and actions is unichain or not. This problem has been proven to be NP-hard. We study this problem while an MDP contains a state which is either recurrent under all deterministic policies or absorbing under some action. We introduce the definitions of avoidable and reach- able sets and provide the corresponding polynomial algorithms that finds the states from which a given set is avoidable or reachable. We also provide a polynomial algorithm that detects whether a state is recurrent and solves the unichain classification problem for an MDP with a recurrent state and a polynomial algorithm for finding all recurrent and stopping states and solving the unichain classification problem with recurrent or stopping states. At the end of the first chapter, we discuss detecting all transient states in an MDP in polynomial time. In the second chapter, we study optimal admission of arrivals to an M/M/k/N queue. The arriving customers are classified into m types, where m ≥ 1. The rewards and holding costs depend on customer types. Upon admitting an arriving customer, the system collects the reward from the admitted customer and pays the hold- ing cost to the admitted customer. We study average reward per unit time for the problem. We prove the existence of an optimal trunk reservation policy and describe the structures of stationary optimal, canonical, bias optimal, and Blackwell optimal policies. If there exist two or more stationary optimal policies, we apply more sensitive optimality criteria to detect the best policy among all stationary optimal policies. We show that bias optimal and Blackwell optimal

关键词： Unichain classification Markov decision process re-current state polynomial algorithm queueing system trunk reservation policy stationary optimal policy canonical policy bias optimal policy Blackwell optimal policy

来源：评论

学校读者我要写书评

暂无评论

Scheduling open shops with parallel machines

引用

Operations Research Letters 1982年第4期1卷 161-164页

作者： Lawler, E.L. Luby, M.G. Vazirani, V.V. Computer Science Division University of California Berkeley CA 94720 United States

The parallel shop and the open shop are two machine environments that have received much attention in the literature of scheduling theory. A common generalization-the open shop with parallel machines-is considered in this paper. polynomial-time algorithms are presented for obtaining minimum-length preemptive schedules for three cases. Open shops with single-operation machines of equal speed are scheduled with essentially no more difficulty than an ordinary open shop. Open shops with multiple-operation machines of equal speed are scheduled with the aid of a sequence of network flow computations. The general open shop problem with parallel machines of arbitrary speeds can be solved by linear programming, in much the same way as an optimal preemptive schedule can be found for unrelated parallel machines. © 1982.

关键词： Open shop parallel machines polynomial algorithm preemptive scheduling

来源：评论

学校读者我要写书评

暂无评论

Cluster-Fault-Tolerant Routing in Burnt Pancake Graphs

Cluster-Fault-Tolerant Routing in Burnt Pancake Graphs

引用

10th International Conference on algorithms and Architectures for Parallel Processing

作者： Iwasawa, Nagateru Watanabe, Tatsuro Iwasaki, Tatsuya Kaneko, Keiichi Tokyo Univ Agr & Technol Grad Sch Engn Koganei Tokyo Japan

ISBN: (纸本)9783642131356

This paper proposes a routing algorithm in an n-burnt pancake graph B(n), which is a topology for interconnection networks, with at most n - 1 faulty clusters whose diameters are at most 3. For an arbitrary pair of non-faulty nodes, the proposed algorithm constructs a fault-free path of length at most 2n + 10 between them in O(n(2)) time complexity.

关键词： Cluster Faults Routing algorithm polynomial algorithm Dependability Interconnection Network Disjoint Paths

来源：评论

学校读者我要写书评

暂无评论

Probabilistické algoritmy pro prvočíselnost

Probabilistické algoritmy pro prvočíselnost

引用

作者： Tejkalová, Natálie Charles University of Prague

Attention has been paid mostly to the new deterministic algorithm for primality testing AKS recently. However, probabilistic algorithms remain an efficient tool for primality testing. Our thesis focuses mostly on two most well-known probabilistic algorithms for primality testing. It describes the main idea and gives proofs of correctness of Solovay-Strassen and Rabin-Miller algorithms. Apart from that, it also tries to look at the subject of probabilistic algorithms from a wider perspective. It presents a definition of a probabilistic algorithm and various complexity classes that correspond to Monte Carlo or Las Vegas algorithms. Besides pure mathematical theory, we mention also some philosophical aspects that need to be considered when we decide to use the probabilistic method. Powered by TCPDF (***)

关键词： Probabilistic algorithm polynomial algorithm prime number

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：