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

An Algorithm for the Feedback Vertex Set Problem on a Normal Helly Circular-Arc Graph

Journal of Computer and Communications 2016年第8期4卷 23-31页

作者： Hirotoshi Honma Yoko Nakajima Atsushi Sasaki Department of Creative Engineering National Institute of Technology Kushiro College Kushiro Japan

The feedback vertex set (FVS) problem is to find the set of vertices of minimum cardinality whose removal renders the graph acyclic. The FVS problem has applications in several areas such as combinatorial circuit design, synchronous systems, computer systems, and very-large-scale integration (VLSI) circuits. The FVS problem is known to be NP-hard for simple graphs, but polynomi-al-time algorithms have been found for special classes of graphs. The intersection graph of a collection of arcs on a circle is called a circular-arc graph. A normal Helly circular-arc graph is a proper subclass of the set of circular-arc graphs. In this paper, we present an algorithm that takes time to solve the FVS problem in a normal Helly circular-arc graph with n vertices and m edges.

关键词： design and analysis of algorithms Feedback Vertex Set Normal Helly Circular-Arc Graphs Intersection Graphs

来源：评论

学校读者我要写书评

暂无评论

Algorithm for Identifying the Maximum Detour Hinge Vertices of a Permutation Graph

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2015年第6期E98A卷 1161-1167页

作者： Honma, Hirotoshi Nakajima, Yoko Igarashi, Yuta Masuyama, Shigeru Kushiro Coll Natl Inst Technol Dept Informat Engn Kushiro Hokkaido 0840916 Japan Kushiro Natl Coll Technol Elect Informat Syst Engn Course Kushiro Hokkaido 0840916 Japan Toyohashi Univ Technol Dept Comp Sci & Engn Toyohashi Aichi 4418580 Japan

A hinge vertex is a vertex in an undirected graph such that there exist two vertices whose removal makes the distance between them longer than before. Identifying hinge vertices in a graph can help detect critical nodes in communication network systems, which is useful for making them more stable. For finding them, an Omicron(n(3)) time algorithm was developed for a simple graph, and, linear time algorithms were developed for interval and permutation graphs, respectively. Recently, the maximum detour hinge vertex problem is defined by Honma et al. For a hinge vertex u in a graph, the detour degree of u is the largest value of distance between any pair of x and y (x and y are adjacent to u) by removing u. A hinge vertex with the largest detour degree in G is defined as the maximum detour hinge vertex of G. This problem is motivated by practical applications, such as network stabilization with a limited cost, i.e., by enhancing the reliability of the maximum detour hinge vertex, the stability of the network is much improved. We previously developed an Omicron(n(2)) time algorithm for solving this problem on an interval graph. In this study, we propose an algorithm that identifies the maximum detour hinge vertex on a permutation graph in Omicron(n(2)) time, where n is the number of vertices in the graph.

关键词： design and analysis of algorithms intersection graphs maximum detour hinge vertex problem permutation graph

来源：评论

学校读者我要写书评

暂无评论

Enhancing the Computation of Distributed Shortest Paths on Power-law Networks in Dynamic Scenarios

引用

THEORY OF COMPUTING SYSTEMS 2015年第2期57卷 444-477页

作者： D'Angelo, Gianlorenzo D'Emidio, Mattia Frigioni, Daniele Romano, Daniele GSSI I-67100 Laquila Italy Univ Laquila Dept Informat Engn Comp Sci & Math I-67100 Laquila Italy Univ Laquila Dept Ind & Informat Engn & Econ I-67100 Laquila Italy

The problem of finding and keeping updated shortest paths in distributed networks is considered crucial in today's practical applications. In the recent past, there has been a renewed interest in devising new efficient distance-vector algorithms as an attractive alternative to link-state solutions for large-scale Ethernet networks, in which scalability and reliability are key issues or the nodes can have limited storage capabilities. In this paper, we present Distributed Computation Pruning (DCP), a new technique, which can be combined with every distance-vector routing algorithm based on shortest paths, allowing to reduce the total number of messages sent by that algorithm and its space occupancy per node. To check its effectiveness, we combined the new technique with DUAL (Diffuse Update ALgorithm), one of the most popular distance-vector algorithm in the literature, which is part of CISCO's widely used EIGRP protocol, and with the recently introduced LFR (Loop Free Routing) which has been shown to have good performances on real networks. We give experimental evidence that these combinations lead to a significant gain both in terms of number of messages sent and of memory requirements per node.

关键词： design and analysis of algorithms Computer communication networks Distributed algorithms Dynamic algorithms Shortest paths Experimental analysis

来源：评论

学校读者我要写书评

暂无评论

Approximating Spanning Trees with Few Branches

引用

THEORY OF COMPUTING SYSTEMS 2015年第1期56卷 181-196页

作者： Chimani, Markus Spoerhase, Joachim Univ Jena Inst Comp Sci Jena Germany Univ Wurzburg Inst Comp Sci D-97070 Wurzburg Germany

Given an undirected, connected graph, the aim of the minimum branch-node spanning tree problem is to find a spanning tree with the minimum number of nodes of degree larger than 2. The problem is motivated by network design problems where junctions are significantly more expensive than simple end- or through-nodes, and are thus to be avoided. Unfortunately, it is NP-hard to recognize instances that admit an objective value of zero, rendering the search for guaranteed approximation ratios futile. We suggest to investigate a complementary formulation, called maximum path-node spanning tree, where the goal is to find a spanning tree that maximizes the number of nodes with degree at most two. While the optimal solutions (and the practical applications) of both formulations coincide, our formulation proves more suitable for approximation. In fact, it admits a trivial 1/2-approximation algorithm. Our main contribution is a local search algorithm that guarantees a ratio of 6/11, as well as showing that the problem is APX-hard, i.e., it does not allow a PTAS.

关键词： Theory of computation design and analysis of algorithms Approximation algorithms analysis Routing and network design problems

来源：评论

学校读者我要写书评

暂无评论

Weight-constrained and density-constrained paths in a tree: Enumerating, counting, and k-maximum density paths

引用

DISCRETE APPLIED MATHEMATICS 2015年 180卷 126-134页

作者： Lee, Chia-Wei Chen, Pin-Liang Hsieh, Sun-Yuan Natl Cheng Kung Univ Dept Comp Sci & Informat Engn Tainan 701 Taiwan Natl Cheng Kung Univ Inst Med Informat Tainan 701 Taiwan Natl Cheng Kung Univ Inst Mfg Informat & Syst Tainan 701 Taiwan

Let T be a tree of n nodes in which each edge is associated with a value and a weight that are a real number and a positive integer, respectively. Given two integers W-min and W-max and two real numbers d(min) and d(max) a path P in a tree is feasible if the sum of the edge weights in P is between W-min and W-max and the ratio of the sum of the edge values in P to the sum of the edge weights in P is between dmin and dm. In this paper, we first present an O(n log(2) n+ h)time algorithm to find all feasible paths in a tree, where h = O(n(2)) if the output of a path is given by its end-nodes. Then, we present an O(n log(2) n)-time algorithm to count the number of all feasible paths in a tree. Finally, we present an O(n log(2) n + h)-time algorithm to find the k feasible paths whose densities are the k largest of all feasible paths. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Counting mode design and analysis of algorithms Feasible paths k-maximum density path problem Network design Trees

来源：评论

学校读者我要写书评

暂无评论

Algorithm for Finding Maximum Detour Hinge Vertices of Interval Graphs

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2014年第6期E97A卷 1365-1369页

作者： Honma, Hirotoshi Nakajima, Yoko Igarashi, Yuta Masuyama, Shigeru Kushiro Natl Coll Technol Dept Informat Engn Kushiro Hokkaido 0840916 Japan Kushiro Natl Coll Technol Elect Informat Syst Engn Course Kushiro Hokkaido 0840916 Japan Toyohashi Univ Technol Dept Comp Sci & Engn Toyohashi Aichi 4418580 Japan

Consider a simple undirected graph G = (V, E) with vertex set V and edge set E. Let G - u be a subgraph induced by the vertex set V - (u). The distance delta(G)(x, y) is defined as the length of the shortest path between vertices x and y in G. The vertex u E V is a hinge vertex if there exist two vertices x, y is an element of V - {u} such that delta(G-u)(x,y) > delta(G)(x, y). Let U be a set consisting of all hinge vertices of G. The neighborhood of u is the set of all vertices adjacent to u and is denoted by N(u). We define d(u) = max{delta(G-u)(x, y) vertical bar delta(G-u)(x, y) > delta G(x, y), x, y is an element of N(u)} for u is an element of U as detour degree of u. A maximum detour hinge vertex problem is to find a hinge vertex u with maximum d(u) in G. In this paper, we proposed an algorithm to find the maximum detour hinge vertex on an interval graph that runs in O(n(2)) time, where n is the number of vertices in the graph.

关键词： design and analysis of algorithms maximum detour hinge vertex problem intersection graphs interval graphs

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

The internal Steiner tree problem: Hardness and approximations

引用

JOURNAL OF COMPLEXITY 2013年第1期29卷 27-43页

作者： Huang, Chao-Wen Lee, Chia-Wei Gao, Huang-Ming Hsieh, Sun-Yuan Natl Cheng Kung Univ Dept Comp Sci & Informat Engn Tainan 701 Taiwan

Given a graph G = (V, E) with a cost function c : E -> R+ and a vertex subset R subset of V, an internal Steiner tree is a Steiner tree that contains all the vertices in R, and such that each vertex in R must be an internal vertex. The internal Steiner tree problem involves finding an internal Steiner tree T whose total cost Sigma((u,v)is an element of E(T)) c(u, v) is the minimum. In this paper, we first show that the internal Steiner tree problem is MAX SNP-hard. We then present a (2 rho + 1)-approximation algorithm for solving the problem on complete graphs, where rho is an approximation ratio for the Steiner tree problem. Currently, the best-known rho is In 4+is an element of < 1.39. Moreover, for the case where the cost of each edge is restricted to being either 1 or 2, we present a 9/7-approximation algorithm for the problem. (c) 2012 Elsevier Inc. All rights reserved.

关键词： VLSI routing Approximation algorithms MAX SNP-hardness Steiner trees The internal Steiner tree problem design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Paging mobile users in cellular networks: Optimality versus complexity and simplicity

引用

THEORETICAL COMPUTER SCIENCE 2013年 470卷 23-35页

作者： Bar-Noy, Amotz Cheilaris, Panagiotis Feng, Yi Golin, Mordecai J. CUNY Dept Comp Sci New York NY 10016 USA Univ Svizzera Italiana Fac Informat Lugano Switzerland Hong Kong Univ Sci & Technol Dept Comp Sci Kowloon Hong Kong Peoples R China

A mobile user is roaming in a zone composed of many cells in a cellular network system. When a call arrives, the system pages the user in these cells since the user never reports its location unless it leaves the zone. Each cell is associated with a positive value which is the probability that the user resides in this cell. A delay constraint requires the user to be found within a predetermined number of paging rounds where in each round a subset of the cells is paged. The goal is to design a paging strategy that minimizes the expected number of paged cells until the user is found. Optimal solutions based on dynamic programming are known. The running time of former implementations is quadratic in the number of cells and linear in the number of rounds. We introduce two implementations whose running times are also linear in the number of cells, by proving that the dynamic programming formulation satisfies properties (like the Monge property) that enable us to use various dynamic programming speed-up techniques. We also propose a new heuristic of almost linear complexity that outperforms a known linear complexity heuristic while running faster when the number of rounds is far less than the number of cells. Our comprehensive simulations compare the non-optimal heuristics with the optimal solutions, demonstrating the trade-off between optimality and running time efficiency as well as implementation simplicity. (C) 2012 Elsevier B.V. All rights reserved.

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

来源：评论

学校读者我要写书评

暂无评论

A Linear-Time Algorithm for Constructing a Spanning Tree on Circular Trapezoid Graphs

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2013年第6期E96A卷 1051-1058页

作者： Honma, Hirotoshi Nakajima, Yoko Aoshima, Haruka Masuyama, Shigeru Kushiro Natl Coll Technol Dept Informat Engn Kushiro Hokkaido 0840916 Japan Kushiro Natl Coll Technol Elect Informat Syst Engn Course Kushiro Hokkaido 0840916 Japan Toyohashi Univ Technol Dept Comp Sci & Engn Toyohashi Aichi 4418580 Japan

Given a simple connected graph G with n vertices, the spanning tree problem involves finding a tree that connects all the vertices of G. Solutions to this problem have applications in electrical power provision, computer network design, circuit analysis, among others. It is known that highly efficient sequential or parallel algorithms can be developed by restricting classes of graphs. Circular trapezoid graphs are proper super-classes of trapezoid graphs. In this paper, we propose an O(n) time algorithm for the spanning tree problem on a circular trapezoid graph: Moreover, this algorithm can be implemented in O(log n) time with O(n/ log n) processors on EREW PRAM computation model.

关键词： design and analysis of algorithms intersection graphs circular trapezoid graphs spanning tree problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：