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

Minimal cutwidth linear arrangements of abelian Cayley graphs

DISCRETE MATHEMATICS 2008年第20期308卷 4670-4695页

作者： Berend, Daniel Korach, Ephraim Lipets, Vladimir Ben Gurion Univ Negev Dept Math IL-84105 Beer Sheva Israel Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel Ben Gurion Univ Negev Dept Ind Engn & Management IL-84105 Beer Sheva Israel

We find the minimal cutwidth and bisection width values for abelian Cayley graphs with up to 4 generators and present an algorithm for finding the corresponding optimal ordering. We also find minimal cuts of each orde... 详细信息

关键词： combinatorial optimization graph algorithm Cayley graphs MINCUT linear arrangement

来源：评论

学校读者我要写书评

暂无评论

EBOARST: An Efficient Edge-Based Obstacle-Avoiding Rectilinear Steiner Tree Construction algorithm

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2008年第12期27卷 2169-2182页

作者： Long, Jieyi Zhou, Hai Memik, Seda Ogrenci Northwestern Univ Dept Elect Engn & Comp Engn Evanston IL 60208 USA

Obstacle-avoiding Steiner routing has arisen as a fundamental problem in the physical design of modern VLSI chips. In this paper, we present EBOARST, an efficient four-step algorithm to construct a rectilinear obstacle-avoiding Steiner tree for a given set of pins and a given set of rectilinear obstacles. Our contributions are fourfold. First, we propose a novel algorithm, which generates sparse obstacle-avoiding spanning graphs efficiently. Second, we present a fast algorithm for the minimum terminal spanning tree construction step, which dominates the running time of several existing approaches. Third, we present an edge-based heuristic, which enables us to perform both local and global refinements, leading to Steiner trees with small lengths. Finally, we discuss a refinement technique called segment translation to further enhance the quality of the trees. The time complexity of our algorithm is O(n log n). Experimental results on various benchmarks show that our algorithm achieves 16.56 times speedup on average, while the average length of the resulting obstacle-avoiding rectilinear Steiner trees is only 0.46% larger than the best existing solution.

关键词： graph algorithm obstacle-avoiding routing Steiner tree

来源：评论

学校读者我要写书评

暂无评论

EBOARST: An Efficient Edge-Based Obstacle-Avoiding Rectilinear Steiner Tree Construction algorithm

EBOARST: An Efficient Edge-Based Obstacle-Avoiding Rectiline...

引用

International Symposium on Physical Design (ISPD)

作者： Long, Jieyi Zhou, Hai Memik, Seda Ogrenci Northwestern Univ Dept Elect Engn & Comp Engn Evanston IL 60208 USA

关键词： graph algorithm obstacle-avoiding routing Steiner tree

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for Variants of Weighted Matching and Assignment Problems

引用

MATHEMATICS IN COMPUTER SCIENCE 2008年第4期1卷 673-688页

作者： Banerjee, Satyajit Chowdhury, Atish Datta Ghosh, Subhas Kumar Honeywell Technol Solut 151-1 DoraisanipalyaBannerghatta Rd Bangalore 560076 Karnataka India

Obtaining a matching in a graph satisfying a certain objective is an important class of graph problems. Matching algorithms have received attention for several decades. However, while there are efficient algorithms to obtain a maximum weight matching, not much is known about the maximum weight maximum cardinality, and maximum cardinality maximum weight matching problems for general graphs. Our contribution in this work is to show that for bounded weight input graphs one can obtain an algorithm for both maximum weight maximum cardinality (for real weights), and maximum cardinality maximum weight matching (for integer weights) by modifying the input and running the existing maximum weight matching algorithm. Also, given the current state of the art in maximum weight matching algorithms, we show that, for bounded weight input graphs, both maximum weight maximum cardinality, and maximum cardinality maximum weight matching have algorithms of similar complexities to that of maximum weight matching. Subsequently, we also obtain approximation algorithms for maximum weight maximum cardinality, and maximum cardinality maximum weight matching.

关键词： Maximum weight maximum cardinality matching approximation algorithm graph algorithm reduction

来源：评论

学校读者我要写书评

暂无评论

An Improved Divide-and-Conquer algorithm for Finding All Minimum k-Way Cuts

引用

19th International Symposium on algorithms and Computations (ISAAC 2008)

作者： Xiao, Mingyu Univ Elect Sci & Technol China Sch Comp Sci arid Engn Chengdu 610054 Peoples R China

ISBN: (纸本)9783540921813

Given a positive integer k and an edge-weighted undirected graph G = (V, E;w), the minimum k-way cut problem is to find a subset of edges of minimum total weight whose removal separates the graph into k connected components. This problem is a natural generalization of the classical minimum cut problem and has been well-studied in the literature. A simple and natural method to solve the minimum k-way cut problem is the divide-and-conquer method: getting a minimum k-way cut by properly separating the graph into two small graphs and then finding minimum k'-way cut and k ''-way cut respectively in the two small graphs, where k' + k '' = k. In this paper, we present the first algorithm for the tight case of k' = [k/2]. Our algorithm runs in O(n(4k-lgk)) time and can enumerate all minimum k-way cuts, which improves all the previously known divide-and-conquer algorithms for this problem.

关键词： k-Way Cut Divide-and-Conquer graph algorithm

来源：评论

学校读者我要写书评

暂无评论

algorithms for multiterminal cuts

引用

3rd International Computer Science Symposium

作者： Xiao, Mingyu Chinese Univ Hong Kong Dept Comp Sci & Engn Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9783540797081

Given a graph G = (V, E) with n vertices and m edges, and a subset T of 1 vertices called terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of k edges (non-terminal vertices), whose removal from G separates each terminal from all the others. These two problems are NP-hard for l >= 3 but well-known to be polynomial-time solvable for 1 = 2 by the flow technique. In this paper, we show that Edge Multiterminal Cut is polynomial-time solvable for k = O(log n) by presenting an O(2(k)lT(n, m)) algorithm, where T(n, m) O(min(n(2/3), m(1/2))m) is the running time of finding a minimum (s,t) cut in an unweighted graph. We also give two algorithms for Vertex Multiterminal Cut that run in O(l(k)T(n, m)) time and O((k!)T-2(n, m)) time respectively. The former one indicates that Vertex Multiterminal Cut is solvable in polynomial time for I being a constant and k = O(log n), and the latter one improves the best known algorithm of running time O(4(k3) n(O(1))). When l = 3, we show that the running times can be improved to O(1.415(k) T(n, m)) for Edge Multiterminal Cut and O(2.059(k)T(n, m)) for Vertex Multiterminal. Cut. Furthermore, we present a simple idea to solve another important problem Multicut by finding minimum multiterminal. cuts. Our algorithms for Multicuts are also faster than the previously best algorithm. Based on a notion farthest minimum isolating cut, we present some properties for Multiterminal Cuts, which help shed light on the structure of optimal cut problems, and enables us to design efficient algorithms for Multiterminal Cuts, as well as some other related cut problems.

关键词： graph algorithm multiterminal cut multicut fixed parameter tractability

来源：评论

学校读者我要写书评

暂无评论

Combined Segmentation and Visual Attention for Object Categorization and Video Semantic Concepts Detection

Combined Segmentation and Visual Attention for Object Catego...

引用

3rd International Conference on Pervasive Computing and Applications

作者： Tan, Li Cao, Yuanda Yang, Minghua He, Qiaoyan Beijing Inst Technol Beijing Lab Intelligent Informat Technol Sch Comp Sci Beijing Peoples R China

ISBN: (纸本)9781424420209

Recent researches show that the benefits of image segmentation have been exploited in object categorization and recognition approaches. In most of these works, objects are segmented from the background around to increase recognition accuracy. However, it is generally hard to find a segmentation that captures all correct object boundaries in images of real world scene. So some researches begin to choose several segmentations for representing the objects and performing object categorization. In this paper, we take advantage of an efficient graph-based algorithm for image segmentation, and combine a visual attention model to locate the salient and effective segmentations in a real world image. We propose a model which extends the Bag-of-features method for modeling the semantic objects. We evaluate our approach on two experiments: multiclass categorization in Caltech 101 datasets and high-level features extraction in video datasets of TRECVID2007. The results show that combining segmentation and visual attention makes our model achieve competitive performance.

关键词： Image Segmentation graph algorithm Visual Attention Object Categorization Semantic Concepts Detection

来源：评论

学校读者我要写书评

暂无评论

A General Tractable Density Concept for graphs

引用

MATHEMATICS IN COMPUTER SCIENCE 2008年第4期1卷 689-699页

作者： Farago, Andras Univ Texas Dallas Dept Comp Sci POB 830688 Richardson TX 75083 USA

In many applications it is an important algorithmic task to find a densest subgraph in an input graph. The complexity of this task depends on how density is defined. If density means the ratio of the number of edges and the number of vertices in the subgraph, then the algorithmic problem has long been known efficiently solvable. On the other hand, the task becomes NP-hard with closely related but somewhat modified concepts of density. To capture many possible tractable density concepts of interest in a common model, we define and analyze a general concept of density, called F-density. Here F is a family of graphs and we are looking for a subgraph of the input graph, such that this subgraph is the densest in terms of containing the highest number of graphs from F relative to the size of the subgraph. We show that for any fixed finite family F, a subgraph of maximum F-density can be found in polynomial time. As our main tool we develop an algorithm, that may be of independent interest, which can find an independent set of maximum independence ratio in a certain class of weighted graphs. The independence ratio is the weight of the independent set divided by the weight of its neighborhood.

关键词： graph algorithm graph density densest subgraph

来源：评论

学校读者我要写书评

暂无评论

Complexity of the Packing Coloring Problem for Trees

Complexity of the Packing Coloring Problem for Trees

引用

34th International Workshop on graph-Theoretic Concepts in Computer Science

作者： Fiala, Jiri Golovach, Petr A. Charles Univ Prague Dept Appl Math CR-11800 Prague Czech Republic Univ Bergen Dept Informat N-5020 Bergen Norway

ISBN: (纸本)9783540922476

Packing coloring is a partitioning of the vertex set of a graph with the property that vertices in the i-th class have pairwise distance greater than i. We solve an open problem of Goddard et al. and show that the decision whether a tree allows a packing coloring with at most k classes is NP-complete. We accompany this NP-hardness result by a polynomial time algorithm for trees for closely related variant of the packing coloring problem where the lower bounds on the distances between vertices inside color classes are determined by an infinite nondecreasing sequence of bounded integers.

关键词： Packing coloring computational complexity graph algorithm chordal graph

来源：评论

学校读者我要写书评

暂无评论

Realization of two graph algorithms and design of the operational platform of graph algorithms

引用

Yi Qi Yi Biao Xue Bao/Chinese Journal of Scientific Instrument 2007年第SUPP. 4期28卷 378-380+387页

作者： Wu, Jun Liu, Xiulan College of Electronic Information and Control Engineering Beijing University of Technology Beijing 100022 China

Two graph algorithms which derive from bread-first search were implemented by using C language in this paper. One algorithm is a replacement method for finding out a graph's all spanning tree, the other is the Paton algorithm for finding out all essential circuit of a graph. This paper mainly introduced the flow of the two graph algorithms. An illustrative example was presented. Also, a practical operational platform of graph algorithm was designed and realized in this paper.

关键词： All spanning tree graph algorithm Operational platform design Paton algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：