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

High-Order Entropy Compressed Bit Vectors with Rank/Select

algorithms 2014年第4期7卷 608-620页

作者： Beskers, Kai Fischer, Johannes Karlsruhe Inst Technol Inst Theoret Informat D-76131 Karlsruhe Germany Tech Univ Dortmund Fak Informat Otto Hahn Straae 14 D-44227 Dortmund Germany

We design practical implementations of data structures for compressing bit-vectors to support efficient rank-queries (counting the number of ones up to a given point). Unlike previous approaches, which either store the bit vectors plainly, or focus on compressing bit-vectors with low densities of ones or zeros, we aim at low entropies of higher order, for example 101010 . . . 10. Our implementations achieve very good compression ratios, while showing only a modest increase in query time.

关键词： design and analysis of algorithms data compression implementation and testing of algorithms

来源：评论

学校读者我要写书评

暂无评论

ON SYNTHESIS OF SCHEDULING algorithms

引用

INFORMATION PROCESSING LETTERS 1984年第3期19卷 147-150页

作者： GUPTA, RG SRIVASTAVA, VSP School of Computer and Systems Sciences Jawaharlal Nehru University New Delhi - 110 067 India

algorithms synthesis is a new approach in the field of design and analysis of algorithms. Darlington (1978) presented a tree structure starting from a high level definition (by defining permutation function) as root-node and finally obtaining 6 terminal-nodes corresponding to each sorting algorithm he discussed. The algorithms-synthesis approach starts from a high level definition and ultimately results in the required algorithms. An attempt is made to synthesize some scheduling algorithms starting, as Darlington did, from a high level definition, and using program transformation techniques. Three scheduling algorithms are taken into the synthesis: 1. First-Come-First-Serve, 2. Round-Robin, and 3. Selfish-Round-Robin. The rules applied are mainly the unfolding-and-folding technique as examined by Burstall and Darlington (1977).

关键词： Synthesis of algorithms design and analysis of algorithms scheduling algorithms

来源：评论

学校读者我要写书评

暂无评论

The Clustered Selected-Internal Steiner Tree Problem

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2022年第1期33卷 55-66页

作者： Chen, Yen Hung Univ Taipei Dept Comp Sci 1 Ai Guo West Rd Taipei 100234 Taiwan

Given a complete graph G = (V,E), with nonnegative edge costs, two subsets R subset of V and R'subset of R, a partition R = {R-1,R-2, ... ,R-k} of R, R-i boolean AND R-j = phi, i not equal j and Script capital R' = {R-1',R-2', ...,R-k'} of R', R-i'subset of R-i, a clustered Steiner tree is a tree T of G that spans all vertices in R such that T can be cut into k subtrees T-i by removing k - 1 edges and each subtree T-i spans all vertices in R-i, 1 <= i <= k. The cost of a clustered Steiner tree is defined to be the sum of the costs of all its edges. A clustered selected-internal Steiner tree of G is a clustered Steiner tree for R if all vertices in R-i' are internal vertices of T-i. The clustered selected-internal Steiner tree problem is concerned with the determination of a clustered selected-internal Steiner tree T for R and R' in G with minimum cost. In this paper, we present the first known approximation algorithm with performance ratio (rho + 4) for the clustered selected-internal Steiner tree problem, where rho is the best-known performance ratio for the Steiner tree problem.

关键词： design and analysis of algorithms approximation algorithms facility allocation in networks clustered Steiner tree selected-internal Steiner tree clustered selected-internal Steiner tree

来源：评论

学校读者我要写书评

暂无评论

On-line maintenance of optimal machine schedules

引用

SADHANA-ACADEMY PROCEEDINGS IN ENGINEERING SCIENCES 1997年第2期22卷 257-279页

作者： Aman, A Balakrishnan, A Chandru, V FMIPA IPB Jalan Raya Padjadjaran Bogor Indonesia Smeal College of Business Administration Penn State University University Park USA Department of Computer Science and Automation Indian Institute of Science Bangalore India

Effective and efficient scheduling in a dynamically changing environment is important for real-time control of manufacturing, computer, and telecommunication systems. This paper illustrates the algorithmic and analytical issues associated with developing efficient and effective methods to update schedules on-line. We consider the problem of dynamically scheduling precedence-constrained jobs on a single processor to minimize the maximum completion time penalty. We first develop an efficient technique to reoptimize a rolling schedule when new jobs arrive. The effectiveness of reoptimizing the current schedule as a long-term on-line strategy is measured by bounding its performance relative to oracles that have perfect information about future job arrivals.

关键词： scheduling design and analysis of algorithms heuristics

来源：评论

学校读者我要写书评

暂无评论

An optimal PRAM algorithm for a spanning tree on trapezoid graphs

引用

Journal of Applied Mathematics and Computing 2003年第1-2期12卷 21-29页

作者： Bera, Debashis Pal, Madhumangal Pal, Tapan K. Dept. Appl. Math. Ocean. Comp. Prog. Vidyasagar University Midnapore-721 102 India

Let G be a graph with n vertices and m edges. The problem of constructing a spanning tree is to find a connected subgraph of G with n vertices and n - 1 edges. In this paper, we propose an O(log n) time parallel algor... 详细信息

关键词： design and analysis of algorithms Parallel algorithms Spanning tree Trapezoid graphs

来源：评论

学校读者我要写书评

暂无评论

Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques

引用

SIAM JOURNAL ON COMPUTING 1996年第3期25卷 540-561页

作者： Kaplan, H Shamir, R TEL AVIV UNIV SACKLER FAC EXACT SCI DEPT COMP SCI IL-69978 TEL AVIV ISRAEL

We study two related problems motivated by molecular biology. Given a graph G and a constant k, does there exist a supergraph G' of G that is a unit interval graph and has clique size at most k? Given a graph G and a proper k-coloring c of G, does there exist a supergraph G' of G that is properly colored by c and is a unit interval graph? We show that those problems are polynomial for fixed k. On the other hand, we prove that the first problem is equivalent to deciding if the bandwidth of G is at most k - 1. Hence, it is NP-hard and W[t]-hard for all t. We also show that the second problem is W[1]-hard. This implies that for fixed k, both of the problems are unlikely to have an O(n(alpha)) algorithm, where alpha is a constant independent of k. A central tool in our study is a new graph-theoretic parameter closely related to pathwidth. An unexpected useful consequence is the equivalence of this parameter to the bandwidth of the graph.

关键词： design and analysis of algorithms parameterized complexity interval graphs bandwidth pathwidth

来源：评论

学校读者我要写书评

暂无评论

Routing of single-source and multiple-source queries in static sensor networks

引用

JOURNAL OF DISCRETE algorithms 2007年第1期5卷 1-11页

作者： Gasieniec, Leszek Su, Chang Wong, Prudence W. H. Xin, Qin Univ Liverpool Dept Comp Sci Liverpool Merseyside England Univ Bergen Dept Informat Bergen Norway

In this paper, we introduce new geometric ad-hoc routing algorithms to route queries in static sensor networks. For singlesource-queries routing, we utilise a centralised mechanism to accomplish a query using an asymptotically optimal number of transmissions O(c), where c is the length of the shortest path between the source and the destination. For multiple-source-queries routing, the number of transmissions for each query is bounded by O(c log n), where n is the number of nodes in the network. For both single-source and multiple-source queries, the routing stage is preceded by preprocessing stages requiring O(nD) and O(n(2)D) transmissions, respectively, where D is the diameter of the network. Our algorithm improves the complexity of the currently best known algorithms in terms of the number of transmissions for each query. The preprocessing is worthwhile if it is followed by frequent queries. We could also imagine that there is an extra initial power (say, batteries) available during the preprocessing stage or alternatively the positions of the sensors are known in advance and the preprocessing can be done before the sensors are deployed in the field. It is also worth mentioning that a lower bound of Omega(c(2)) transmissions has been proved if preprocessing is not allowed [***, ***, ***, Asymptotically optimal geometric mobile ad-hoc routing, in: Proceedings of the Sixth International Workshop on Discrete Algorithm and Methods for Mobility, Atlanta, GA, September 2002, pp. 24-33]. (C) 2006 Elsevier B.V. All rights reserved.

关键词： Wireless sensor network Geometric routing Communication design and analysis of algorithms Memory constraint

来源：评论

学校读者我要写书评

暂无评论

REPRESENTATIONS OF GRAPHS ON A CYLINDER

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 1991年第1期4卷 139-149页

作者： TAMASSIA, R TOLLIS, IG UNIV TEXAS DEPT COMP SCIRICHARDSONTX 75080

A complete characterization of the class of graphs that admit a cylindric visibility representation is presented, where vertices are represented by intervals parallel to the axis of the cylinder and the edges correspond to pairs of visible intervals. Moreover, linear time algorithms are given for testing the existence of and constructing such a representation. Important applications of cylindric visibility representations can be found in the layout of regular VLSI circuits, such as linear systolic arrays and bit-slice architectures. Also, alternative "dual" characterizations are presented of the graphs that admit visibility representations in the plane and in the cylinder. It is interesting to observe that neither of these two classes is contained in the other, although they have a nonempty intersection.

关键词： VISIBILITY GRAPH VISIBILITY REPRESENTATION design and analysis of algorithms COMPUTATIONAL GEOMETRY CYLINDER PLANAR GRAPH CATERPILLAR

来源：评论

学校读者我要写书评

暂无评论

Strongly polynomial-time truthful mechanisms in one shot

Strongly polynomial-time truthful mechanisms in one shot

引用

2nd International Workshop on Internet and Network Economic

作者： Penna, Paolo Proietti, Guido Widmayer, Peter Univ Salerno Dipartimento Informat & Applicaz Renato M Capocel Salerno Italy ETH Inst Theoret Informat Zurich Switzerland Univ Aquila Dipartimento Informat I-67100 Laquila Italy CNR Ist Anal Sistemi & Informat A Ruberti Rome Italy

ISBN: (纸本)3540681388

One of the main challenges in algorithmic mechanism design is to turn (existing) efficient algorithmic Solutions into efficient truthful mechanisms. Building a truthful mechanism is indeed a difficult process since the underlying algorithm must obey certain "monotonicity" properties and suitable payment functions need to be computed (this task usually represents the bottleneck in the overall time complexity). We provide a general technique for building truthful mechanisms that provide optimal solutions in strongly polynomial time. We show that the entire mechanism can be obtained if one is able to express/write a strongly polynomial-time algorithm (for the corresponding optimization problem) as a "suitable combination" of simpler algorithms. This approach applies to a wide class of mechanism design graph problems, where each selfish agent corresponds to a weighted edge in a graph (the weight of the edge is the cost of using that edge). Our technique can be applied to several optimization problems which prior results cannot handle (e.g., MIN-MAX optimization problems). As an application, we design the first (strongly polynomial-time) truthful mechanism for the minimum diameter spanning tree problem, by obtaining it directly from an existing algorithm for solving this problem. For this non-utilitarian MIN-MAX problem, no truthful mechanism was known, even considering those running in exponential time (indeed, exact algorithms do not necessarily yield truthful mechanisms). Also, standard techniques for payment computations may result in a running time which is not polynomial in the size of the input graph. The overall running time of our mechanism, instead, is polynomial in the number n of nodes and in of edges, and it is only a factor O(n alpha(n, n)) away from the best known canonical centralized algorithm. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Algorithmic game theory Mechanism design design and analysis of algorithms Minimum diameter spanning tree

来源：评论

学校读者我要写书评

暂无评论

Optimal discovery of repetitions in 2D

引用

DISCRETE APPLIED MATHEMATICS 2005年第1-3期151卷 5-20页

作者： Apostolico, A Brimkov, VE Univ Padua Dipartimento Ingn Informat I-35131 Padua Italy Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA SUNY Coll Buffalo Dept Math Buffalo NY 14222 USA

Repetitive substructures in two-dimensional arrays emerge in speeding up searches and have been recently studied also independently in an attempt to parallel some of the classical derivations concerning repetitions in strings. The present paper focuses on repetitions in two dimensions that manifest themselves in form of two "tandem" occurrences of a same primitive rectangular pattern W where the two replicas touch each other with either one side or corner. Being primitive here means that W cannot be expressed in turn by repeated tiling of another array. The main result of the paper is an O(n(3) log n) algorithm for detecting all "side-sharing" repetitions in an n x n array. This is optimal, based on bounds on the number of such repetitions established in previous work. With easy adaptations, these constructions lead to an equally optimal, O(n(4)) algorithm for repetitions of the second type. (c) 2005 Elsevier B.V. All rights reserved.

关键词： design and analysis of algorithms pattern matching pattern discovery 2D arrays tandem repetition

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：