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

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

来源：评论

学校读者我要写书评

暂无评论

Complexity and algorithms for Semipaired Domination in graphs 30th

Complexity and Algorithms for Semipaired Domination in Graph...

引用

30th International Workshop on Combinatorial algorithms (IWOCA)

作者： Henning, Michael A. Pandey, Arti Tripathi, Vikash Univ Johannesburg Dept Math & Appl Math ZA-2006 Auckland Pk South Africa Indian Inst Technol Ropar Dept Math Nangal Rd Rupnagar 140001 Punjab India

ISBN: (纸本)9783030250041;9783030250058

For a graph G = (V, E) with no isolated vertices, a set D subset of V is called a semipaired dominating set of G if (i) D is a dominating set of G, and (ii) D can be partitioned into two element subsets such that the vertices in each two element set are at distance at most two. The minimum cardinality of a semipaired dominating set of G is called the semipaired domination number of G, and is denoted by gamma(pr2)(G). The MINIMUM SEMIPAIRED DOMINATION problem is to find a semipaired dominating set of G of cardinality gamma(pr2)(G). In this paper, we initiate the algorithmic study of the MINIMUM SEMIPAIRED DOMINATION problem. We show that the decision version of the MINIMUM SEMIPAIRED DOMINATION problem is NP-complete for bipartite graphs and chordal graphs. On the positive side, we present a linear-time algorithm to compute a minimum cardinality semipaired dominating set of interval graphs. We also propose a 1 + ln(2 Delta + 2)-approximation algorithm for the Minimum Semipaired Domination problem, where Delta denotes the maximum degree of the graph and show that the MINIMUM SEMIPAIRED DOMINATION problem cannot be approximated within (1 - c) ln vertical bar V vertical bar for any c > 0 unless P = NP.

关键词： Domination Semipaired domination Bipartite graphs Chordal graphs Interval graphs graph algorithm NP-complete Approximation 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

来源：评论

学校读者我要写书评

暂无评论

Divide & Conquer: I/O Efficient Depth-First Search 15

Divide & Conquer: I/O Efficient Depth-First Search

引用

ACM SIGMOD International Conference on Management of Data

作者： Zhang, Zhiwei Yu, Jeffrey Xu Qin, Lu Shang, Zechao Chinese Univ Hong Kong Hong Kong Peoples R China Univ Technol FEIT Ctr QCIS Sydney NSW Australia

ISBN: (纸本)9781450327589

Depth-First Search (DFS), which traverses a graph in the depth-first order, is one of the fundamental graph operations, and the result of DFS over all nodes in G is a spanning tree known as a D ES-Tree. There are many graph algorithms that need DFS such as connected component computation, topological sort, community detection, eulerian path computation, graph bipartiteness testing, planar graph testing, etc, because the in-memory DFS algorithm shows it can be done in linear time w.r.t. the size of G. However, given the fact that real-world graphs grow rapidly in the big data era, the in-memory DFS algorithm cannot be used to handle a large graph that cannot be entirely held in main memory. In this paper, we focus on I/O efficiency and study semi-external algorithms to DFS a graph G which is on disk. Here, like the existing semi-external algorithms, we assume that a spanning tree of G can be held in main memory and the remaining edges of G are kept on disk, and compute the DFS-Tree in main memory with which DFS can be identified. We propose novel divide & conquer algorithms to DFS over a graph G on disk. In brief, we divide a graph into several subgraphs, compute the DFS-Tree for each subgraph independently, and then merge them together to compute the DES-Tree for the whole graph. With the global DES-Tree computed we identify DFS. We discuss the valid division, that can lead to the correct DFS, and the challenges to do so. We propose two division algorithms, named Divide-Star and Divide-TD, and a merge algorithm. We conduct extensive experimental studies using four real massive datasets and several synthetic datasets to confirm the I/O efficiency of our approach.

关键词： graph algorithm I/O Efficient Depth-first Search

来源：评论

学校读者我要写书评

暂无评论

Eight-neighborhood sparse contour extraction in binary images 27

Eight-neighborhood sparse contour extraction in binary image...

引用

27th International Conference on Computer Supported Cooperative Work in Design (CSCWD)

作者： Chen, Danyi Cao, Weinian Rao, Shengxiang Luo, Lijun Tongji Univ Sch Software Engn Shanghai Peoples R China Fudan Univ Zhongshan Hosp Shanghai Peoples R China Tongji Univ Stomatol Hosp Shanghai Peoples R China

ISBN: (纸本)9798350349184;9798350349191

Edge detection of objects in images is a longstanding challenge in computer vision. Traditional edge detection methods for grayscale images exhibit strong generalization but often yield unsatisfactory results when applied to binary images. Currently, contour extraction algorithms based on binary images may fail to ensure strict semantic integrity within the sparse 8-neighborhood or may result in contours with low accuracy. Faced with the limitations of currently existing edge detection and contour extraction algorithms, a novel graph-traversal-based algorithm was proposed to extract the 8-neighborhood sparse contour of binary images, while the higher accuracy is held as well. Initially, we eliminate noise regions in binary images that do not correspond to the main objects and solidify foreground objects to create an approximate outer contour while removing outlier areas. Subsequently, we fine-tune the candidate contour pixel sets to obtain the final sparse outer contour. Additionally, we extend the algorithm to achieve inner contour extraction and contour extraction for multiple non-interfering foreground entities. Experimental evaluations of the algorithm are conducted on the LiTS17 dataset and compared with state-of-the-art edge extraction and contour tracing algorithms, as well as the latest binary image 8-neighborhood sparse contour extraction algorithms. The proposed algorithm exhibits a 22.3% improvement in accuracy despite a 32% runtime increase, with higher or equivalent accuracy in all individual images and no degradation observed. (code: https://***/nianwuluo/ct-liver-CSCWD)

关键词： Edge detection Contour tracing Computational geometry Binary image graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Emergency Evacuation Assistance 14

Emergency Evacuation Assistance

引用

14th International Conference on Ubiquitous Information Management and Communication (IMCOM)

作者： Lee, John Koo, Dan Tadesse, Dinaol Jain, Atharv Shettar, Sushmitha Kim, Dongsoo Indiana Univ Purdue Univ Dept Elect & Comp Engn Indianapolis IN 46202 USA Indiana Univ Purdue Univ Dept Engn Technol Construct Management Program Indianapolis IN 46202 USA Jackson State Univ Comp Engn Dept Jackson MS USA Univ Texas Dallas Comp Sci Dept Dallas TX USA

ISBN: (纸本)9781728154534

There have been more than necessary casualties due to a lack of intelligence in emergency evacuation mechanisms such as exit signs. Although large or complex buildings and facilities have many exit doors, in case of emergency, people may not be able to escape quickly enough due to sudden loss of directions and difficulty in finding safe routes to exit doors. If you were ever in such a situation, you would wish that if there were ever smart escape route assistance mechanisms available or at least smart exit signs available that safely and quickly guide you to a safe haven. It is what we try to make such a wish come true. In this paper, we propose a graph mapping scheme and a new safe evacuation route algorithm for safe emergency evacuation assistance, with the aid of recent technology called Internet of Things (IoT). The gist of our approach is that people are not allowed to pass through or even go towards any area where fire or toxic gas is detected by controlling the direction signals installed on exit signs. The experiments performed with our methodology shows that the proposed technology may be able to save more lives.

关键词： fire safety emergency evacuation IoT graph algorithm

来源：评论

学校读者我要写书评

暂无评论

A Supernodal All-Pairs Shortest Path algorithm 20

A Supernodal All-Pairs Shortest Path Algorithm

引用

25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP)

作者： Sao, Piyush Kannan, Ramakrishnan Gera, Prasun Vuduc, Richard Oak Ridge Natl Lab Oak Ridge TN 37830 USA Georgia Inst Technol Atlanta GA 30332 USA

ISBN: (纸本)9781450368186

We show how to exploit graphs parsity in the Floyd-Warshall algorithm for the all-pairs shortest path (Apsp) problem. FLOYD-WARSHALL is an attractive choice for Apsp on high-performing systems due to its structural similarity to solving dense linear systems and matrix multiplication. However, if sparsity of the input graph is not properly exploited, Floyd-Warshall will perform unnecessary asymptotic work and thus may not be a suitable choice for many input graphs. To overcome this limitation, the key idea in our approach is to use the known algebraic relationship between Floyd-Warshall and Gaussian elimination, and import several algorithmic techniques from sparse Cholesky factorization, namely, fill-in reducing ordering, symbolic analysis, supernodal traversal, and elimination tree parallelism. When combined, these techniques reduce computation, improve locality and enhance parallelism. We implement these ideas in an efficient shared memory parallel prototype that is orders of magnitude faster than an efficient multi-threaded baseline Floyd-Warshall that does not exploit sparsity. Our experiments suggest that the Floyd-Warshall algorithm can compete with Dijkstra's algorithm (the algorithmic core of Johnson's algorithm) for several classes sparse graphs.

关键词： graph algorithm sparse matrix computations shared-memory parallelism communication-avoiding algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Almost automatic method for reconstruction 3D geometric model of the left ventricle from 3D+1D precordial echocardiogram

Almost automatic method for reconstruction 3D geometric mode...

引用

Medical Imaging 2001 Conference

作者： Ching, YT Liu, YH Chang, CL Chen, JSJ Natl Chiao Tung Univ Dept Comp & Informat Sci Hsinchu 30050 Taiwan

ISBN: (纸本)0819440078

Echocardiography is the most convenient means for both physicians and patients for heart disease diagnosis. The 3D+1D echocardiogram. provides important information for evaluation of the 3D heart function such as the ejection fraction or wall motion. The most basic task to evaluate such functions of a heart is to segment left ventricles and reconstruct the the 3D geometric model of left ventricle from a set of echocardiographic images. Since there are many images involved, the method should not need too many user assists. In this work, we design a method for reconstructing the left ventricles with very few user assists.

关键词： echocardiogram 3D model left ventricle snake model alpha-shape graph algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：