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

Linear Time algorithms for Finding Articulation and Hinge Vertices of Circular Permutation Graphs

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2013年第3期E96D卷 419-425页

作者： Honma, Hirotoshi Abe, Kodai Nakajima, Yoko Masuyama, Shigeru Kushiro Natl Coll Technol Dept Informat Engn Kushiro Hokkaido 0840916 Japan Univ Tsukuba Dept Intelligent Interact Technol Tsukuba Ibaraki 3058577 Japan Toyohashi Univ Technol Dept Comp Sci & Engn Toyohashi Aichi 4418580 Japan

Let G(s) = (V-s, E-s) be a simple connected graph. A vertex v is an element of V-s is an articulation vertex if deletion of v and its incident edges from G(s) disconnects the graph into at least two connected components. Finding all articulation vertices of a given graph is called the articulation vertex problem. A vertex u is an element of V-s is called a hinge vertex if there exist any two vertices x and y in G(s) whose distance increase when u is removed. Finding all hinge vertices of a given graph is called the hinge vertex problem. These problems can be applied to improve the stability and robustness of communication network systems. In this paper, we propose linear time algorithms for the articulation vertex problem and the hinge vertex problem of circular permutation graphs.

关键词： design and analysis of algorithms articulation vertices hinge vertices circular permutation graphs

来源：评论

学校读者我要写书评

暂无评论

An efficient label setting/correcting shortest path algorithm

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2012年第1期51卷 437-455页

作者： Sedeno-Noda, Antonio Gonzalez-Martin, Carlos Univ La Laguna DEIOC Tenerife 38205 Spain

We design a new label shortest path algorithm by applying the concept of a pseudo permanent label. This approach allows an algorithm to partition the set of nodes into two new sets: pseudo permanently labeled nodes and its complementary set. From this point of view, this new label method can be considered as a label setting method. Moreover, at least one node becomes permanently labeled when some nodes which belong to the set of pseudo permanently labeled nodes are scanned in each iteration of the algorithm. In the case of networks with non-negative length arcs it is easy to prove that this node has the minimum distance label among the non-pseudo permanently labeled nodes. On the other hand, it is not known during the computation which pseudo permanently labeled nodes are permanently labeled. Therefore, all distance labels are temporary and the algorithm becomes a label correcting method. Nevertheless, the proposed algorithm exhibits some nice features, such as: (1) the time bound for the running of the algorithm for a network with n nodes and m arcs is O(nm);(2) the number of node scan operations in the algorithm is less than the number of these operations in the previous label correcting algorithms as is observed in the computational experience;(3) the algorithm incorporates two new rules which allow easy detection of a negative cycle in the network;(4) the algorithm is quite simple and very easy to implement, and does not require sophisticated data structures;(5) the algorithm exhibits flexibility in the order in which the new pseudo permanently labeled nodes are scanned. The above features are possible through the application of the pseudo permanent label concept.

关键词： Network/Graphs Distance algorithms design and analysis of algorithms Pseudo permanent labels

来源：评论

学校读者我要写书评

暂无评论

PATTERN MATCHING WITH SWAPS IN PRACTICE

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2012年第2期23卷 323-342页

作者： Campanelli, Matteo Cantone, Domenico Faro, Simone Giaquinta, Emanuele Univ Catania Scuola Super Catania I-95123 Catania Italy Univ Catania Dipartimento Matemat & Informat I-95125 Catania Italy

The Pattern Matching problem with Swaps consists in finding all occurrences of a pattern P in a text T, when disjoint local swaps in the pattern are allowed. In the Approximate Pattern Matching problem with Swaps one seeks, for every text location with a swapped match of P, the number of swaps necessary to obtain a match at the location. In this paper we devise two general algorithms for both Standard and Approximate Pattern Matching with Swaps, named CROSS-SAMPLING and BACKWARD-CROSS-SAMPLING, with a O(nm) and O(nm(2)) worst-case time complexity, respectively. Then we provide efficient implementations of them, based on bit-parallelism, which achieve O(n) and O(nm) worst-case time complexity, with patterns v-hose length is comparable to the word-size of the target machine. From an extensive comparison with. some of the most Live algorithms for the matching problem, it turns out that our algorithms a) very flexible and achieve very good results in practice.

关键词： Approximate pattern matching with swaps nonstandard pattern matching combinatorial algorithms on words design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

An Algorithm for Minimum Feedback Vertex Set Problem on a Trapezoid Graph

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2011年第6期E94A卷 1381-1385页

作者： Honma, Hirotoshi Kitamura, Yutaro Masuyama, Shigeru Kushiro Natl Coll Technol Dept Informat Engn Kushiro Hokkaido 0840916 Japan Univ Tsukuba Dept Intelligent Interact Technol Tsukuba Ibaraki 3058577 Japan Toyohashi Univ Technol Dept Comp Sci & Engn Toyohashi Aichi 4418580 Japan

In an undirected graph, the feedback vertex set (FVS for short) problem is to find a set of vertices of minimum cardinality whose removal makes the graph acyclic. The FVS has applications to several areas such that combinatorial circuit design, synchronous systems, computer systems, VLSI circuits and so on. The FVS problem is known to be NP-hard on general graphs but interesting polynomial solutions have been found for some special classes of graphs. In this paper, we present an 0(n(2.68) + gamma n) time algorithm for solving the FVS problem on trapezoid graphs, where gamma is the total number of factors included in all maximal cliques.

关键词： design and analysis of algorithms feedback vertex set trapezoid graphs NP-hard

来源：评论

学校读者我要写书评

暂无评论

Constructing independent spanning trees for locally twisted cubes

引用

THEORETICAL COMPUTER SCIENCE 2011年第22期412卷 2237-2252页

作者： Liu, Yi-Jiun Lan, James K. Chou, Well Y. Chen, Chiuyuan Natl Chiao Tung Univ Dept Appl Math Hsinchu 300 Taiwan

The independent spanning trees (ISTs) problem attempts to construct a set of pairwise independent spanning trees and it has numerous applications in networks such as data broadcasting, scattering and reliable communication protocols. The well-known ISTs conjecture, Vertex/Edge Conjecture, states that any n-connected/n-edge-connected graph has n vertex-ISTs/edge-ISTs rooted at an arbitrary vertex r. It has been shown that the Vertex Conjecture implies the Edge Conjecture. In this paper, we consider the independent spanning trees problem on the n-dimensional locally twisted cube LTQ(n). The very recent algorithm proposed by Hsieh and Tu (2009) [12] is designed to construct n edge-ISTs rooted at vertex 0 for LTQ(n). However, we find out that LTQ(n) is not vertex-transitive when n >= 4;therefore Hsieh and Tu's result does not solve the Edge Conjecture for LTQ(n),,. In this paper, we propose an algorithm for constructing n vertex-ISTs for LTQ(n);consequently, we confirm the Vertex Conjecture (and hence also the Edge Conjecture) for LTQ(n),. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Independent spanning trees Data broadcasting design and analysis of algorithms Locally twisted cubes Hypercubes Hypercube variants Parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximate Pattern Matching with the L₁, L₂ and L∞ Metrics

引用

ALGORITHMICA 2011年第2期60卷 335-348页

作者： Lipsky, Ohad Porat, Ely Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel

Given an alphabet I ={1,2 pound,aEuro broken vertical bar,|I |} pound text string TaI pound (n) and a pattern string PaI pound (m) , for each i=1,2,aEuro broken vertical bar,n-m+1 define L (p) (i) as the p-norm distance when the pattern is aligned below the text and starts at position i of the text. The problem of pattern matching with L (p) distance is to compute L (p) (i) for every i=1,2,aEuro broken vertical bar,n-m+1. We discuss the problem for d=1,2,a. First, in the case of L (1) matching (pattern matching with an L (1) distance) we show a reduction of the string matching with mismatches problem to the L (1) matching problem and we present an algorithm that approximates the L (1) matching up to a factor of 1+epsilon, which has an O (1/epsilon 2nlogm log vertical bar Sigma vertical bar) run time. Then, the L (2) matching problem (pattern matching with an L (2) distance) is solved with a simple O(nlog m) time algorithm. Finally, we provide an algorithm that approximates the L (a) matching up to a factor of 1+epsilon with a run time of O (1/epsilon 2nlogm log vertical bar Sigma vertical bar). We also generalize the problem of String Matching with mismatches to have weighted mismatches and present an O(nlog (4) m) algorithm that approximates the results of this problem up to a factor of O(log m) in the case that the weight function is a metric.

关键词： design and analysis of algorithms Combinatorial algorithms on words Approximate string matching Hamming distance

来源：评论

学校读者我要写书评

暂无评论

New complexity bounds for image matching under rotation and scaling

引用

JOURNAL OF DISCRETE algorithms 2011年第1期9卷 122-136页

作者： Hundt, Christian Liskiewicz, Maciej Univ Rostock Inst Informat Rostock Germany Univ Lubeck Inst Theoret Informat Lubeck Germany

Image matching under rotation is a computational problem to determine for two given images A and B a rotation of A that most accurately resembles B. The research in combinatorial pattern matching led to a series of improved algorithms which commonly solve this problem by a sophisticated search in the set of all rotations of A. This paper provides the lower bound Omega(n3) on the worst case cardinality of this set for images of size n x n and presents the first optimal algorithm of such kind, i.e., one that solves image matching under rotations in time Omega(n(3)). Moreover, for image matching under compositions of rotation and scaling a new lower bound Omega(n(6)/log n) on the worst case cardinality of the set of rotated and scaled transformations of an n x n image is provided. This bound almost matches the upper bound Omega(n(6)). (C) 2010 Elsevier B.V. All rights reserved.

关键词： Digital image matching Combinatorial pattern matching Discrete rotations and scalings design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

The weight-constrained maximum-density subtree problem and related problems in trees

引用

JOURNAL OF SUPERCOMPUTING 2010年第3期54卷 366-380页

作者： Hsieh, Sun-Yuan Chou, Ting-Yu Natl Cheng Kung Univ Dept Comp Sci & Informat Engn Tainan 701 Taiwan

Given a tree T = (V, E) of n nodes such that each node v is associated with a value-weight pair (val(v), w(v)), where value val(v) is a real number and weight w(v) is a non-negative integer, the density of T is defined as Sigma(v is an element of V) val(v)/Sigma(v is an element of V) w(v). A subtree of T is a connected subgraph (V', E') of T, where V' subset of V and E' subset of E. Given two integers w(min) and w(max), the weight-constrained maximum-density subtree problem on T is to find a maximum-density subtree T' = (V', E') satisfying w(min) <= Sigma(v is an element of V')w(v) <= W-max. In this paper, we first present an O(w(max)n)-time algorithm to find a weight-constrained maximum-density path in a tree T, and then present an O (w(max)(2)n)-time algorithm to find a weight-constrained maximum-density subtree in T. Finally, given a node subset S subset of V, we also present an O(w(max)(2)n)-time algorithm to find a weight-constrained maximum-density subtree in T which covers all the nodes in S.

关键词： design and analysis of algorithms Maximum-density paths Maximum-density Steiner trees Maximum-density subtrees NP-completeness Pseudo-polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast computation of a longest increasing subsequence and application

引用

INFORMATION AND COMPUTATION 2010年第9期208卷 1054-1059页

作者： Crochemore, Maxime Porat, Ely Kings Coll London London WC2R 2LS England Univ Paris Est Paris France Bar Ilan Univ IL-52900 Ramat Gan Israel

We consider the complexity of computing a longest increasing subsequence (LIS) parameterised by the length of the output. Namely, we show that the maximal length k of an increasing subsequence of a permutation of the set of integers {1, 2, ..., n) can be computed in time O(n log log k) in the RAM model, improving the previous 30-year bound of O(n log k). The algorithm also improves on the previous O(n log log n) bound. The optimality of the new bound is an open question. Reducing the computation of a longest common subsequence (LCS) between two strings to an LIS computation leads to a simple O(n log log n)-time algorithm for two sequences having r pairs of matching symbols and an LCS of length k. Crown Copyright (C) 2010 Published by Elsevier Inc. All rights reserved.

关键词： design and analysis of algorithms Longest increasing subsequence Longest common subsequence Data structures Priority queue Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Area-Feature Boundary Labeling¹

引用

COMPUTER JOURNAL 2010年第6期53卷 827-841页

作者： Bekos, Michael A. Kaufmann, Michael Potika, Katerina Symvonis, Antonios Natl Tech Univ Athens Sch Appl Math & Phys Sci Athens 15780 Greece Univ Tubingen Inst Informat D-72076 Tubingen Germany

Boundary labeling is a relatively new labeling method. It can be useful in automating the production of technical drawings and medical drawings, where it is common to explain certain parts of the drawing with text labels, arranged on its boundary so that other parts of the drawing are not obscured. In boundary labeling, we are given a rectangle R which encloses a set of n sites. Each site s is associated with an axis-parallel rectangular label l(s). The labels must be placed in distinct positions on the boundary of R and they must be connected to their corresponding sites with polygonal lines, called leaders, so that the labels are pairwise disjoint and the leaders do not intersect each other. In this paper, we study a version of the boundary labeling problem where the sites can 'float' within a polygonal region. We present a polynomial time algorithm, which runs in O(n(3)) time and produces a labeling of minimum total leader length for labels of uniform size placed in fixed positions on the boundary of rectangle R.

关键词： boundary labeling map labeling design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：