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

Minimum consistent subset of simple graph classes

DISCRETE APPLIED MATHEMATICS 2023年第1期338卷 255-277页

作者： Dey, Sanjana Maheshwari, Anil Nandy, Subhas C. Indian Stat Inst ACM Unit Kolkata India Carleton Univ Sch Comp Sci Ottawa ON Canada

In the minimum consistent subset (MCS) problem, a connected simple undirected graph G = (V, E) is given whose each vertex is colored by one of the colors {c1, c2, ... , ck}, and the objective is to compute a minimum size subset C & SUBE;V such that for each vertex v & ISIN;V, its set of nearest neighbors in C (with respect to the hop-distance) contains at least one vertex of the same color as v. The decision version of the MCS problem is NP complete for general graphs. Even for planar graphs, the problem remains NP-complete. We will consider some simple graph classes like path, spider, caterpillar and comb;and present polynomial-time algorithms.& COPY;2023 Elsevier B.V. All rights reserved.

关键词： Minimum consistent subset Graphs optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

A MINIMUM AREA VLSI NETWORK FOR O(LOG N) TIME SORTING

引用

IEEE TRANSACTIONS ON COMPUTERS 1985年第4期34卷 336-343页

作者： BILARDI, G PREPARATA, FP UNIV ILLINOIS COORDINATED SCI LABURBANAIL 61801

A generalization of a known class of parallel sorting algorithms is presented, together with a new interconnection to execute them. A VLSI implementation is also proposed, and its area-time performance is discussed. It is shown that an algorithm in the class is executable in O(log n) time by a chip occupying O(n2) area. The design is a typical instance of a ``hybrid architecture,"" resulting from the combination of well-known VLSI networks as the orthogonal trees and the cube-connected cycles; it also provably meets the AT2 = Â¿(n2 log2 n) lower bound for sorters of n words of length (1 + Â¿) log n (Â¿ ≫ 0).

关键词： Area-time tradeoff bitonic merging combination sorting cube-connected cycles mesh optimal algorithms orthogonal trees parallel computation

来源：评论

学校读者我要写书评

暂无评论

Mathematical complexity of running filters on semi-groups and related problems

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2008年第7期56卷 3191-3197页

作者： Coltuc, Dinu Valahia Univ Targoviste Dept Elect Engn Bucharest Romania INP GIPSA Lab Grenoble France

This paper proves that the mathematical complexity of running filters on semi-groups is C(p) = 3 - (6/(p + 1)) operations per sample, where p is the filter window. On other algebraic structures, the mathematical complexity of the filtering can be lower. Two such cases are investigated: the running filtering on max/min lattice and on additions group. They correspond to max/min and moving average filters. It is shown that the algorithms developed for semi-groups are of interest in such cases, too. Thus, the fastest deterministic algorithm for max/min filtering known so far is based on an algorithm for running filtering on semi-groups. First, an optimized version is proposed in this paper. Then, further improvement for data-dependent max/min algorithms is proposed. Finally, the case of moving average and exponential smoothing is investigated. Their implementation by using the algorithms for semi-groups is of lower complexity than the classical recursive implementation for the particular case of small size windows (p = 3 and p = 4).

关键词： fast algorithms fast max/min filters fast moving average mathematical complexity optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

A space and time efficient algorithm for SimRank computation

引用

WORLD WIDE WEB-INTERNET AND WEB INFORMATION SYSTEMS 2012年第3期15卷 327-353页

作者： Yu, Weiren Zhang, Wenjie Lin, Xuemin Zhang, Qing Le, Jiajin Univ New S Wales Sch Comp Sci & Engn Sydney NSW 2052 Australia Australia CSIRO ICT Ctr E Hlth Res Ctr Herston Qld 4029 Australia Donghua Univ Sch Comp Sci & Technol Shanghai Peoples R China

SimRank has become an important similarity measure to rank web documents based on a graph model on hyperlinks. The existing approaches for conducting SimRank computation adopt an iteration paradigm. The most efficient deterministic technique yields O(n(3)) worst-case time per iteration with the space requirement O(n(2)), where n is the number of nodes (web documents). In this paper, we propose novel optimization techniques such that each iteration takes O(min {n . m . n(t)}) time and O(n + m) space, where m is the number of edges in a web-graph model and r <= log 7. In addition, we extend the similarity transition matrix to prevent random surfers getting stuck, and devise a pruning technique to eliminate impractical similarities for each iteration. Moreover, we also develop a reordering technique combined with an over-relaxation method, not only speeding up the convergence rate of the existing techniques, but achieving I/O efficiency as well. We conduct extensive experiments on both synthetic and real data sets to demonstrate the efficiency and effectiveness of our iteration techniques.

关键词： graph similarity SimRank link-based analysis optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

Load-balancing spatially located computations using rectangular partitions

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2012年第10期72卷 1201-1214页

作者： Saule, Erik Bas, Erdeniz O. Catalyuerek, Uemit V. Ohio State Univ Dept Biomed Informat Columbus OH 43212 USA Ohio State Univ Dept Comp Sci & Engn Columbus OH 43212 USA Ohio State Univ Dept Elect & Comp Engn Columbus OH 43212 USA

Distributing spatially located heterogeneous workloads is an important problem in parallel scientific computing. We investigate the problem of partitioning such workloads (represented as a matrix of non-negative integers) into rectangles, such that the load of the most loaded rectangle (processor) is minimized. Since finding the optimal arbitrary rectangle-based partition is an NP-hard problem, we investigate particular classes of solutions: rectilinear, jagged and hierarchical. We present a new class of solutions called m-way jagged partitions, propose new optimal algorithms for m-way jagged partitions and hierarchical partitions, propose new heuristic algorithms, and provide worst case performance analyses for some existing and new heuristics. Moreover, the algorithms are tested in simulation on a wide set of instances. Results show that two of the algorithms we introduce lead to a much better load balance than the state-of-the-art algorithms. We also show how to design a two-phase algorithm that reaches different time/quality tradeoffs. (C) 2012 Elsevier Inc. All rights reserved.

关键词： Load balancing Spatial partitioning optimal algorithms Heuristics Dynamic programming Particle-in-cell Mesh-based computation Jagged partitioning Rectilinear partitioning Hierarchical partitioning

来源：评论

学校读者我要写书评

暂无评论

CODE ASSIGNMENT FOR HIDDEN TERMINAL INTERFERENCE AVOIDANCE IN MULTIHOP PACKET RADIO NETWORKS

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 1995年第4期3卷 441-449页

作者： BERTOSSI, AA BONUCCELLI, MA UNIV PISA DIPARTIMENTO INFORMAT I-56100 PISA ITALY

Hidden terminal interference is caused by the (quasi-) simultaneous transmission of two stations that cannot hear each other, but are both received by the same destination station, This interference lowers the system throughput and increases the average packet delay, Some random access protocols that reduce this interference have been proposed, e.g., BTMA protocol, However, the hidden terminal interference can be totally avoided only by means of code division multiple access (CDMA) schemes, In this paper, we investigate the problem of assigning orthogonal codes to stations so as to eliminate the hidden terminal interference, Since the codes share the fixed channel capacity allocated to the network in the design stage, their number must not exceed a given bound. In this paper, we seek for assignments that minimize the number of codes used, We show that this problem is NP-complete, and thus computationally intractable, even for very restricted but very realistic network topologies. Then, we present optimal algorithms for further restricted topologies, as well as fast suboptimal centralized and distributed heuristic algorithms, The results of extensive simulation set up to derive the average performance of the proposed heuristics on realistic network topologies are presented.

关键词： Code Division Multiple Access Channel Capacity Network Topology Packet Radio Networks Radiofrequency Interference Delays Minimisation Computational Complexity Interference Suppression Hidden Terminal Interference Avoidance Multihop Packet Radio Networks Code Assignment System Throughput Average Packet Delay Code Division Multiple Access Orthogonal Codes Channel Capacity NP Complete Problem Network Topologies optimal algorithms Distributed Heuristic algorithms Suboptimal Centralized algorithms Network Topology Access Protocols Multiaccess Communication Throughput Delay Interference Elimination Channel Capacity Computer Networks Heuristic algorithms Computational Modeling

来源：评论

学校读者我要写书评

暂无评论

Optimizing some constructions with bars: new geometric knapsack problems

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第3期31卷 1160-1173页

作者： Bereg, S. Diaz-Banez, J. M. Flores-Penaloza, D. Langerman, S. Perez-Lantero, P. Urrutia, J. Univ Texas Dallas Dept Comp Sci Richardson TX 75083 USA Univ Seville Dept Matemat Aplicada 2 Seville Spain Univ Nacl Autonoma Mexico Fac Ciencias Ciudad De Mexico Mexico ULB Dept Informat Brussels Belgium Univ Valparaiso Escuela Ingn Civil Informat Valparaiso Chile Univ Nacl Autonoma Mexico Inst Matemat Ciudad De Mexico Mexico

A set of vertical bars planted on given points of a horizontal line defines a fence composed of the quadrilaterals bounded by successive bars. A set of bars in the plane, each having one endpoint at the origin, defines an umbrella composed of the triangles bounded by successive bars. Given a collection of bars, we study how to use them to build the fence or the umbrella of maximum total area. We present optimal algorithms for these constructions. The problems introduced in this paper are related to the Geometric Knapsack problems (Arkin et al. in Algorithmica 10:399-427, 1993) and the Rearrangement Inequality (Wayne in Scripta Math 12(2):164-169, 1946).

关键词： Geometric optimization Combinatorial optimization Inequalities optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

Parallel merging with restriction

引用

JOURNAL OF SUPERCOMPUTING 2008年第1期43卷 99-104页

作者： Bahig, Hazem M. Ain Shams Univ Dept Math Div Comp Sci Fac Sci Cairo Egypt

In this paper, we study the merging of two sorted arrays A = (a(1), a(2), ..., a(n1)) and B = (b(1), b(2), ..., b(n2)) on EREW PRAM with two restrictions: (1) The elements of two arrays are taken from the integer range [1, n], where n = Max(n(1), n(2)). (2) The elements are taken from either uniform distribution or non-uniform distribution such that #{a is an element of A and b is an element of B s.t.a, b is an element of [(i - 1)n/p + 1, i n/p]} = O(n/p), for 1 <= i <= p (number of processors). We give a new optimal deterministic algorithm runs in O(n/p) time using p processors on EREW PRAM. For p = n/log((g)) n;the running time of the algorithm is O(log((g)) n) which is faster than the previous results, where log((g)) n = loglog((g-1)) n for g > 1 and log((1)) n = log n. We also extend the domain of input data to [1, n(k)], where k is a constant.

关键词： parallel algorithms optimal algorithms integer merging EREW PRAM

来源：评论

学校读者我要写书评

暂无评论

Using knowledge to optimally achieve coordination in distributed systems

引用

THEORETICAL COMPUTER SCIENCE 1999年第1期220卷 31-65页

作者： Neiger, G Bazzi, RA Arizona State Univ Dept Comp Sci & Engn Tempe AZ 85287 USA Intel Corp MicroComp Res Labs Hillsboro OR 97124 USA

A distributed computing system consists of a set of individual processors that communicate through some medium. Coordinating the actions of such processors is essential in distributed computing. Researchers have long endeavored to find efficient solutions to a variety of coordination problems. Recently, processor knowledge has been used to characterize such solutions and to derive more efficient ones. Most of this work has concentrated on the relationship between common knowledge and simultaneous coordination. This paper considers non-simultaneous coordination problems. The results of this paper add to our understanding of the relationship between knowledge and the different requirements of coordination problems. This paper considers the ideas of optimal and optimum solutions to a coordination problem and precisely characterizes the problems for which optimum solutions exist. This characterization is based on combinations of eventual common knowledge and continual common knowledge. The paper then considers more general problems, for which optimal, but no optimum, solutions exist. It defines a new form of knowledge, called extended knowledge, which combines eventual and continual knowledge, and shows how extended knowledge can be used to both characterize and construct optimal protocols for coordination. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： knowledge common knowledge distributed coordination optimal algorithms optimum algorithms

来源：评论

学校读者我要写书评

暂无评论

Generalized Kraft's inequality and discrete k-modal search

引用

SIAM JOURNAL ON COMPUTING 1996年第2期25卷 420-447页

作者： Mathur, A Reingold, EM Univ of Illinois at Urbana-Champaign Urbana IL USA

A function f : R --> R is k-modal if its kth derivative has a unique zero. We study the problem of finding the smallest possible interval containing the unique zero of the kth derivative of such a function, assuming that the function is evaluated only at integer points. We present optimal algorithms for the case when k is even and for k = 3 and near-optimal algorithms when k greater than or equal to 5 and odd. A novel generalization of Kraft's inequality is used to prove lower bounds on the number of function evaluations required. We show how our algorithms lead to an efficient divide-and-conquer algorithm to determine all turning points or zeros of a k-modal function. Unbounded k-modal search is introduced and some problems in extending previous approaches for unbounded searching to the k-modal case are discussed.

关键词： k-modal search Kraft's inequality k-modal functions optimal algorithms binary search unimodal search bimodal search unbounded search Fibonacci numbers

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：