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

A FORBIDDEN MINOR CHARACTERIZATION AND RELIABILITY OF A CLASS OF PARTIAL 4-TREES

NETWORKS 1995年第3期25卷 139-146页

作者： LINGNER, GT POLITOF, T SATYANARAYANA, A CONCORDIA UNIV MONTREALPQCANADA STEVENS INST TECHNOL HOBOKENNJ 07030

This paper characterizes a class G of partial 4-trees in terms of a set of seven forbidden miners. The class G contains several known classes of graphs, including both Delta - Y and Y - Delta graphs. A set of six graph reduction operations is defined, and it is shown that a graph G is an element of G iff G can be reduced to an edgeless graph by a finite sequence of these operations. The all-terminal reliability R(G) of a graph G is the probability that G is connected. The characterization of G is used to develop an O(n log n) algorithm to compute R(G) for all n-point graphs in G. The running time is O(n) for planar graphs in G. (C) 1995 John Wiley and Sons, Inc.

关键词： linear-time algorithm Terminal reliability Partial 3-trees Free networks Complexity Planar Graphs Tree Compute Complexity finite sequence Discrete-time algorithm REGULATORY GUIDE Planar

来源：评论

学校读者我要写书评

暂无评论

COMPUTING MINIMAL SPANNING SUBGRAPHS IN linear-time

引用

SIAM JOURNAL ON COMPUTING 1995年第6期24卷 1332-1358页

作者： HAN, XF KELSEN, P RAMACHANDRAN, V TARJAN, R MAX PLANCK INST INFORMAT D-66123 SAARBRUCKENGERMANY UNIV TEXAS DEPT COMP SCIAUSTINTX 78712 PRINCETON UNIV DEPT COMP SCIPRINCETONNJ 08544 NEC RES INST PRINCETONNJ 08540

Let P be a property of undirected graphs. We consider the following problem: given a graph G that has property P, find a minimal spanning subgraph of G with property P. We describe general algorithms for this problem and prove their correctness under fairly weak assumptions about P. We establish that the worst-case running time of these algorithms is Theta(m + n log n) for 2-edge-connectivity and biconnectivity where II and m denote the number of vertices and edges, respectively, in the input graph. By refining the basic algorithms we obtain the first linear time algorithms for computing a minimal 2-edge-connected spanning subgraph and for computing a minimal biconnected spanning subgraph. We also devise general algorithms for computing a minimal spanning subgraph in directed graphs. These algorithms allow us to simplify an earlier algorithm of Gibbons, Karp, Ramachandran, Soroker, and Tarjan for computing a minimal strongly connected spanning subgraph. We also provide the first tight analysis of the latter algorithm, showing that its worst-case time complexity is Theta(m + n log n).

关键词： MINIMAL SUBGRAPHS BICONNECTIVITY 2-EDGE-CONNECTIVITY STRONG CONNECTIVITY linear-time algorithm WORST-CASE BEHAVIOR

来源：评论

学校读者我要写书评

暂无评论

2 MACHINE OPEN SHOP SCHEDULING PROBLEM TO MINIMIZE AN ARBITRARY MACHINE USAGE REGULAR PENALTY-FUNCTION

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1993年第3期70卷 391-404页

作者： SHAKHLEVICH, NV STRUSEVICH, VA ERASMUS UNIV ROTTERDAM POB 1738 3000 DR ROTTERDAM NETHERLANDS BYELORUSSIAN ACAD SCI INST ENGN CYBERNET MINSK 220012 BELARUS

The paper present a linear-time algorithm for solving the two machine open shop scheduling problem to minimize an arbitrary regular penalty function depending on the lengths of periods during which the machines are us... 详细信息

关键词： OPEN SHOP SCHEDULING MACHINE USAGE PENALTY FUNCTION linear-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A linear-time algorithm FOR SOLVING CONTINUOUS MAXIMIN KNAPSACK-PROBLEMS

引用

OPERATIONS RESEARCH LETTERS 1991年第1期10卷 23-26页

作者： KUNO, T KONNO, H ZEMEL, E TOKYO INST TECHNOL INST HUMAN & SOCIAL SCITOKYO 152JAPAN NORTHWESTERN UNIV JL KELLOGG GRAD SCH MANAGEMENTEVANSTONIL 60208

This paper introduces a special class of mathematical programming problem which maximizes the minimal value of a set of linear functions subject to a single linear constraint and upper bounding constraint on each vari... 详细信息

关键词： linear MAXIMIN PROBLEM CONTINUOUS KNAPSACK PROBLEM linear-time algorithm BINARY SEARCH

来源：评论

学校读者我要写书评

暂无评论

A linear-time algorithm FOR FINDING APPROXIMATE SHORTEST COMMON SUPERSTRINGS

引用

algorithmICA 1990年第3期5卷 313-323页

作者： UKKONEN, E 1. Department of Computer Science University of Helsinki Teollisuuskatu 23 SF-00510 Helsinki Finland

Approximate shortest common superstrings for a given setR of strings can be constructed by applying the greedy heuristics for finding a longest Hamiltonian path in the weighted graph that represents the pairwise overlaps between the strings inR. We develop an efficient implementation of this idea using a modified Aho-Corasick string-matching automaton. The resulting common superstring algorithm runs in timeO(n) or in timeO(n min(logm, log|Σ|)) depending on whether or not the goto transitions of the Aho-Corasick automaton can be implemented by direct indexing over the alphabet Σ. Heren is the total length of the strings inR andm is the number of such strings. The best previously known method requires timeO(n logm) orO(n logn) depending on the availability of direct indexing.

关键词： Shortest common superstring Approximation algorithm linear-time algorithm Greedy heuristics Hamiltonian path

来源：评论

学校读者我要写书评

暂无评论

MINIMIZING EXTERNAL WIRES IN GENERALIZED SINGLE-ROW ROUTING

引用

IEEE TRANSACTIONS ON COMPUTERS 1992年第6期41卷 771-776页

作者： BLAIR, JRS LLOYD, EL UNIV DELAWARE DEPT COMP SCINEWARKDE 19716

Much of the recent work on the automated design of VLSI chips has concentrated on routing problems associated with such designs. One major class of routing problems focuses on single-row routing. Recently, the traditional single-row routing model has been generalized to allow external wires. Under this generalized model, it is possible to route many more single-row routing instances than in the traditional model. There is, however, a clear disadvantage in the use of external wires. since they force a lengthening of the channels surrounding the single row of terminals. Thus, it is desirable for these generalized single-row routings to use a minimum number of external wires. In this note, we provide a linear-time algorithm for determining the minimum number of external wires needed to route a given instance of single-row routing.

关键词： GENERALIZED SINGLE-ROW ROUTING linear-time algorithm MINIMIZATION OF EXTERNAL WIRES SINGLE LAYER VLSI DESIGN

来源：评论

学校读者我要写书评

暂无评论

DETERMINISTIC DECOMPOSITION OF RECURSIVE GRAPH CLASSES

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 1991年第4期4卷 481-501页

作者： BORIE, RB PARKER, RG TOVEY, CA GEORGIA INST TECHNOL SCH IND & SYST ENGNATLANTAGA 30332

The Popular class of series-parallel graphs can be built recursively from single edges by combining smaller components via connections only at a fixed pair of vertices called terminals. This recursive construction property with a limited number of terminals is essential to the linear time solution of problems on these graphs. A second useful property of these graphs is that decomposition is deterministic with respect to the series-parallel rules. This implies that the parse-tree of decomposition (which is required by the algorithms) can be determined in a straightforward manner by repeatedly applying the decomposition rules. Subject to retaining these properties, we examine how far the series-parallel graphs can be generalized. Corollaries of our results yield the deterministic decomposition of the series-parallel and Halin graph classes.

关键词： SERIES-PARALLEL GRAPH DECOMPOSITION RECURSIVE GRAPH CLASS DYNAMIC PROGRAMMING linear-time algorithm

来源：评论

学校读者我要写书评

暂无评论

SOME CHAIN VISIBILITY PROBLEMS IN A SIMPLE POLYGON

引用

algorithmICA 1990年第4期5卷 485-507页

作者： LEE, SH CHWA, KY KOREA INST SCI & TECHNOL DEPT COMP SCI SEOUL 130650 SOUTH KOREA

In this paper, the notions of convex chain visibility and reflex chain visibility of a simple polygonP are introduced, and some optimal algorithms concerned with convex- and reflex-chain visibility problems are described. For a convex-chain visibility problem, two linear-time algorithms are exhibited for determining whether or notP is visible from a given convex chain; one is the turn-checking approach and the other is the decomposition approach based on checking edge visibilities. We also present a linear-time algorithm for finding, if any, all maximal convex chains of a given polygonP from whichP is visible, where a maximal convex chain is a convex chain which does not properly include any other convex chains. It can be made by showing that there can be at most four visible maximal convex chains inP with an empty kernel. By similar arguments, we show that the same problems for reflex chain visibility can be easily solved in linear time.

关键词： Computational geometry Simple polygon Visibility linear-time algorithm

来源：评论

学校读者我要写书评

暂无评论

EMBEDDING RECTIlinear GRAPHS IN linear time

引用

INFORMATION PROCESSING LETTERS 1988年第2期29卷 75-79页

作者： HOFFMANN, F KRIEGEL, K ACAD SCI GDR KARL WEIERSTRASS INST MATHDDR-1086 BERLINGER DEM REP

The class of rectilinear graphs, respectively embedded rectilinear graphs, was introduced by Budach (1978) and examined in the context of maze solving problems. These classes of graphs were independently redefined by Vijayan and Wigderson (1985), who were motivated by very large-scale integration (VLSI) layout design problems. They proved a linear time algorithm to check the embeddability of rectilinear graphs and an O (n squared) time algorithm to generate an embedding of any given rectilinear graph on n nodes. A linear-time algorithm is developed to recognize and embed graphs that are embeddable on the plane using a different and surprisingly simple layout strategy. The strategy uses convex faces. The algorithm is well-suited for implementation because of the reasonable constant behind its O(n) time behavior.

关键词： Rectilinear graph graph embedding linear-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A NEW TRIANGULATION-linear CLASS OF SIMPLE POLYGONS

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1987年第2期22卷 135-147页

作者： LEE, SH CHWA, KY EWHA WOMANS UNIV DEPT COMP SCISEODAEMUN KUSEOUL 120SOUTH KOREA

A new polygon class taking linear-time and space for triangulation, called an if-polygon, is defined. After describing an algorithm for triangulating this class, we show that some triangulation-linear classes previously known, such as a convex polygon, a spiral polygon, an edge-visible polygon and a chain-visible polygon have the same property, called the if-property, as the newly defined class. Consequently, a monotone-separable polygon and a star-shaped polygon can be considered as a union of two if-polygons, respectively. Also, we present a modified algorithm for triangulating a star-shaped polygon without decomposition. As a result, the algorithm is simpler to implement and easier to understand and its correctness can be easily verified.

关键词： Triangulation triangulation-linear class simple polygon linear-time algorithm time complexity 1.3.5. [Computer Graphics] Computational Geometry and Object Modeling-geometric algorithms languages and systems F.2.2.[Analysis of algorithms and Problems-geometrical problems and computations

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：