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

A Two-Player Coalition Cooperative Scheme for the Bodyguard Allocation Problem

Journal of Computer Science & Technology 2018年第4期33卷 823-837页

作者： Jose Alberto Fernandez-Zepedu Daniel Brubeck-Salcedo Daniel Fajardo-Delgado Hector Zatarain-Aceves Department of Computer Science Center for Scientific Research and Higher Education of Ensenada Ensenada BC 22860 Mexico Department of Systems and Computation Instituto Technol6gico de Ciudad Guzmdn Guzmdn JAL 49100 Mexico

We address the bodyguard allocation problem （BAP）, an optimization problem that illustrates the conflict of interest between two classes of processes with contradictory preferences within a distributed system. While a class of processes prefers to minimize its distance to a particular process called the root, the other class prefers to maximize it; at the same time, all the processes seek to build a communication spanning tree with the maximum social welfare. The two state-of-the-art algorithms for this problem always guarantee the generation of a spanning tree that satisfies a condition of Nash equilibrium in the system; however, such a tree does not necessarily produce the maximum social welfare. In this paper, we propose a two-player coalition cooperative scheme for BAP, which allows some processes to perturb or break a Nash equilibrium to find another one with a better social welfare. By using this cooperative scheme, we propose a new algorithm called FFC-BAPs for BAP. We present both theoretical and empirical analyses which show that this algorithm produces better quality approximate solutions than former algorithms for BAP.

关键词： bodyguard allocation problem coalitional game graph algorithm Nash equilibrium

来源：评论

学校读者我要写书评

暂无评论

Greedy algorithms for generalized k-rankings of paths

引用

INFORMATION PROCESSING LETTERS 2010年第22期110卷 979-985页

作者： Zemke, Andrew James, Sandra Narayan, Darren A. Rochester Inst Technol Sch Math Sci Rochester NY 14623 USA Concordia Univ Dept Math St Paul MN 55104 USA

A k-ranking of a graph is a labeling of the vertices with positive integers 1,2, ..., k so that every path connecting two vertices with the same label contains a vertex of larger label. An optimal ranking is one in which k is minimized. Let P-n, be a path with n vertices. A greedy algorithm can be used to successively label each vertex with the smallest possible label that preserves the ranking property. We seek to show that when a greedy algorithm is used to label the vertices successively from left to right, we obtain an optimal ranking. A greedy algorithm of this type was given by Bodlaender et al. in 1998 [1] which generates an optimal k-ranking of P-n. In this paper we investigate two generalizations of rankings. We first consider bounded (k, s)-rankings in which the number of times a label can be used is bounded by a predetermined integer s. We then consider k(t)-rankings where any path connecting two vertices with the same label contains t vertices with larger labels. We show for both generalizations that when G is a path, the analogous greedy algorithms generate optimal k-rankings. We then proceed to quantify the minimum number of labels that can be used in these rankings. We define the bounded rank number (r,s)(G) to be the smallest number of labels that can be used in a (k, s)-ranking and show for n 2, (r,s)(P-n) = [ ((n (2 1))/s)] + i where i = [log(2)(s)] + 1. We define the k(t)-rank number, (t)(r)(G) to be the smallest number of labels that can be used in a k(t)-ranking. We present a recursive formula that gives the k(t)-rank numbers for paths, showing 1;.(P-j) n for all a(n-1) < j <= a(n) where {a(n)) is defined as follows: a(l) = 1 and a(n) = a(n) = [((t + 1)/t)a(n-1)] + 1. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Rank number Ordered coloring Minimal ranking Vertex coloring Greedy algorithm graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Low-cost heuristics for matrix bandwidth reduction combined with a Hill-Climbing strategy

引用

RAIRO-OPERATIONS RESEARCH 2021年第4期55卷 2247-2264页

作者： Gonzaga de Oliveira, Sanderson L. Silva, Liberio M. Univ Fed Lavras Lavras Brazil

This paper studies heuristics for the bandwidth reduction of large-scale matrices in serial computations. Bandwidth optimization is a demanding subject for a large number of scientific and engineering applications. A heuristic for bandwidth reduction labels the rows and columns of a given sparse matrix. The algorithm arranges entries with a nonzero coefficient as close to the main diagonal as possible. This paper modifies an ant colony hyper-heuristic approach to generate expert-level heuristics for bandwidth reduction combined with a Hill-Climbing strategy when applied to matrices arising from specific application areas. Specifically, this paper uses low-cost state-of-the-art heuristics for bandwidth reduction in tandem with a Hill-Climbing procedure. The results yielded on a wide-ranging set of standard benchmark matrices showed that the proposed strategy outperformed low-cost state-of-the-art heuristics for bandwidth reduction when applied to matrices with symmetric sparsity patterns.

关键词： Bandwidth reduction sparse matrix ant colony optimization hyper-heuristic reordering algorithms renumbering ordering graph labeling graph algorithm local search procedure Hill-Climbing procedure

来源：评论

学校读者我要写书评

暂无评论

Strong minimum energy -hop rooted topology for hierarchical wireless sensor networks

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2015年第4期30卷 1077-1094页

作者： Panda, B. S. Shetty, D. Pushparaj Indian Inst Technol Delhi Dept Math Comp Sci & Applicat Grp New Delhi 110016 India

Given a set of sensors, the strong minimum energy topology (SMET) problem is to assign transmit power to each sensor such that the sum of the transmit powers of all the sensors is minimum subject to the constraint that the resulting topology containing only bidirectional links is strongly connected. This problem is known to be NP-hard. However, most of the wireless sensor networks are hierarchical in nature, where shorter path lengths are preferred for communication between any two nodes. Given a set of sensors and a specified sensor, say , the strong minimum energy -hop rooted topology problem (h-SMERT) is to assign transmit power to each sensor such that the sum of the transmit powers of all the sensors is minimum subject to the constraints that the resulting topology containing only bidirectional links is strongly connected and the length of the path from to any other node is at most . We prove that the h-SMERT problem is NP-hard. We also prove that h-SMERT problem is APX-hard. We then show that h-SMERT problem is not approximable within a factor of 1/2 (1 - epsilon) unless NP subset of D T I M E (n(log log n)) On the positive side, we propose a -2(1 + ln n)-approximation algorithm for the h-SMERT problem. We also study two special cases of the h-SMERT problem, namely, the -rest-h-SMERT problem and the -int-h-SMERT problem. We propose a -approximation algorithm for the -rest-h-SMERT problem. The -int-h-SMERT problem is NP-hard for arbitrary . However, for fixed constant , we propose a -approximation algorithm for the -int-h-SMERT problem and obtain a polynomial time optimal algorithm for the -int-h-SMERT problem for k = 2.

关键词： Wireless sensor network Topology control problem Transmission power assignment graph algorithm NP-hard APX-hard Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Cyclic Action graphs for goal recognition problems with inaccurately initialised fluents

引用

KNOWLEDGE AND INFORMATION SYSTEMS 2024年第2期66卷 1257-1300页

作者： Harman, Helen Simoens, Pieter Univ Ghent Imec Dept Informat Technol IDLab Technol Pk 126 B-9052 Ghent Belgium Univ Lincoln Sch Comp Sci Lincoln Ctr Autonomous Syst L CAS Lincoln LN6 7TS England

Goal recognisers attempt to infer an agent's intentions from a sequence of observed actions. This is an important component of intelligent systems that aim to assist or thwart actors;however, there are many challenges to overcome. For example, the initial state of the environment could be partially unknown, and agents can act suboptimally and observations could be missing. Approaches that adapt classical planning techniques to goal recognition have previously been proposed, but, generally, they assume the initial world state is accurately defined. In this paper, a state is inaccurate if any fluent's value is unknown or incorrect. Our aim is to develop a goal recognition approach that is as accurate as the current state-of-the-art algorithms and whose accuracy does not deteriorate when the initial state is inaccurately defined. To cope with this complication, we propose solving goal recognition problems by means of an Action graph. An Action graph models the dependencies, i.e. order constraints, between all actions rather than just actions within a plan. Leaf nodes correspond to actions and are connected to their dependencies via operator nodes. After generating an Action graph, the graph's nodes are labelled with their distance from each hypothesis goal. This distance is based on the number and type of nodes traversed to reach the node in question from an action node that results in the goal state being reached. For each observation, the goal probabilities are then updated based on either the distance the observed action's node is from each goal or the change in distance. Our experimental results, for 15 different domains, demonstrate that our approach is robust to inaccuracies within the defined initial state.

关键词： Goal recognition graph algorithm Cyclic graph Inferring intent Context aware

来源：评论

学校读者我要写书评

暂无评论

DETERMINING CONNECTED COMPONENTS IN LINEAR TIME BY A LINEAR NUMBER OF PROCESSORS

引用

INFORMATION PROCESSING LETTERS 1987年第6期25卷 401-406页

作者： PEPER, F Faculty of Mathematics and Informatics Delft University of Technology P.O. Box 356 2600 AJ Delft The Netherlands

Parallel algorithms for the problem of finding the connected components of a simple undirected graph are examined. These algorithms can be divided into 3 classes: 1. those that generally require a shared memory single instruction streams, multiple data streams (SIMD) model permitting read conflicts on the same memory location, 2. parallelizations of the algorithms operating on matrices, generally using SIMD processors with local memory connected by a regular network, and 3. those that use processors arranged in a binary tree. A lighthouse algorithm is described that has no loss in efficiency and can be used on a shared memory SIMD model. Read conflicts are permitted on the model, but simultaneous write operations or simultaneous write and read operations are not. In the lighthouse algorithm, each processor cyclically reads all of its neighbors' labels and compares them with its own label. The analysis indicates that the lighthouse algorithm efficiently determines the connected components in a graph.

关键词： Parallel processing graph algorithm transitive closure connected component graph theory

来源：评论

学校读者我要写书评

暂无评论

Partitioning vertices into in- and out-dominating sets in digraphs

引用

DISCRETE APPLIED MATHEMATICS 2020年 285卷 43-54页

作者： Nakamura, Kosuke Araki, Toru Gunma Univ Div Elect & Informat Kiryu Gunma 3768515 Japan

For a connected graph, it is known that there exists a partition of the vertex set into two dominating sets of the graph. However, for a digraph, there does not always exist such partition of the vertex set. We consider the problem of determining whether there is a partition of the vertex set into in- and out-dominating sets of the digraph. In this paper, we obtain the following results: (1) The decision problem is NP-complete even if a given digraph is acyclic, and (2) for an oriented tree, there is a polynomial time algorithm for deciding the existence of such partition. (C) 2020 Elsevier B.V. All rights reserved.

关键词： graph algorithm Domination Digraph In-domination Out-domination Domatic partition

来源：评论

学校读者我要写书评

暂无评论

Source location problem with flow requirements in directed networks

引用

OPTIMIZATION METHODS & SOFTWARE 2003年第4期18卷 427-435页

作者： Ito, H Makino, K Arata, K Honami, S Itatsu, Y Fujishige, S Osaka Univ Grad Sch Engn Sci Div Syst Sci Osaka Japan Kyoto Univ Grad Sch Math Dept Commun & Comp Engn Kyoto Japan Matsushita Commun Ind Co Ltd Yokohama Kanagawa Japan Kyoto Univ Math Sci Res Inst Kyoto Japan

Given a directed graph G = (V, A) with a capacity function c : A --> R+, two demand functions d(-), d(+) : V --> R+, and a cost function w : V --> R+, we consider the problem of computing a minimum-cost set S subset of or equal to V such that, for each vertex v is an element of V - S, the arc-connectivity from S to v is at least d(-)(v) and the arc-connectivity from v to S is at least d(+)(v). We present a polynomial time algorithm for the problem where d(-) and d(+) are uniformly fixed and w is uniform. Furthermore, we show that the problem is NP-hard, even if either the cost function or the demand function is uniform.

关键词： graph algorithm arc-connectivity location problem network flow deficient set tree hypergraph

来源：评论

学校读者我要写书评

暂无评论

A Linear Time algorithm for L(2,1)-Labeling of Trees

引用

algorithmICA 2013年第3期66卷 654-681页

作者： Hasunuma, Toru Ishii, Toshimasa Ono, Hirotaka Uno, Yushi Univ Tokushima Dept Math & Nat Sci Tokushima 7708502 Japan Hokkaido Univ Grad Sch Econ Div Modern Econ & Business Adm Sapporo Hokkaido 0600809 Japan Kyushu Univ Dept Econ Engn Fukuoka 8128581 Japan Osaka Prefecture Univ Grad Sch Sci Dept Math & Informat Sci Sakai Osaka 5998531 Japan

An L(2,1)-labeling of a graph G is an assignment f from the vertex set V(G) to the set of nonnegative integers such that |f(x)-f(y)|a parts per thousand yen2 if x and y are adjacent and |f(x)-f(y)|a parts per thousand yen1 if x and y are at distance 2, for all x and y in V(G). A k-L(2,1)-labeling is an L(2,1)-labeling f:V(G)->{0,aEuro broken vertical bar,k}, and the L(2,1)-labeling problem asks the minimum k, which we denote by lambda(G), among all possible assignments. It is known that this problem is NP-hard even for graphs of treewidth 2, and tree is one of very few classes for which the problem is polynomially solvable. The running time of the best known algorithm for trees had been O(Delta (4.5) n) for more than a decade, and an O(min{n (1.75),Delta (1.5) n})-time algorithm has appeared recently, where Delta and n are the maximum degree and the number of vertices of an input tree, however, it has been open if it is solvable in linear time. In this paper, we finally settle this problem by establishing a linear time algorithm for L(2,1)-labeling of trees. Furthermore, we show that it can be extended to a linear time algorithm for L(p,1)-labeling with a constant p.

关键词： Frequency/channel assignment graph algorithm L(2,1)-Labeling Vertex coloring

来源：评论

学校读者我要写书评

暂无评论

Swapping labeled tokens on graphs

引用

THEORETICAL COMPUTER SCIENCE 2015年 586卷 81-94页

作者： Yamanaka, Katsuhisa Demaine, Erik D. Ito, Takehiro Kawahara, Jun Kiyomi, Masashi Okamoto, Yoshio Saitoh, Toshiki Suzuki, Akira Uchizawa, Kei Uno, Takeaki Iwate Univ Dept Elect Engn & Comp Sci Morioka Iwate 0208551 Japan MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan Nara Inst Sci & Technol Grad Sch Informat Sci Ikoma Nara 6300192 Japan Yokohama City Univ Int Coll Arts & Sci Kanazawa Ku Yokohama Kanagawa 2360027 Japan Univ Electrocommun Dept Commun Engn & Informat Chofu Tokyo 1828585 Japan Kobe Univ Grad Sch Engn Nada Ku Kobe Hyogo 6578501 Japan Yamagata Univ Grad Sch Sci & Engn Yonezawa Yamagata 9928510 Japan Natl Inst Informat Principles Informat Res Div Chiyoda Ku Tokyo 1018430 Japan

Consider a puzzle consisting of n tokens on an n-vertex graph, where each token has a distinct starting vertex and a distinct target vertex it wants to reach, and the only allowed transformation is to swap the tokens on adjacent vertices. We prove that every such puzzle is solvable in O(n(2)) token swaps, and thus focus on the problem of minimizing the number of token swaps to reach the target token placement. We give a polynomial-time 2-approximation algorithm for trees, and using this, obtain a polynomial-time 2 alpha-approximation algorithm for graphs whose tree a-spanners can be computed in polynomial time. Finally, we show that the problem can be solved exactly in polynomial time on complete bipartite graphs. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Approximation Complete bipartite graph graph algorithm Sorting network Tree

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：