For a weighted graph with n vertices and m edges, the Minimum k-Way Cut problem is to find a partition of the vertices into k sets that minimizes the total weight of edges crossing the sets. We obtain several important structural properties of minimum multiway cuts and use them to design efficient algorithms for several multiway partition problems. We design the first algorithm for finding minimum 3-way cuts in hypergraphs, which runs in O(dmn 3) time, where d is the sum of the degrees of all the vertices. We also give an O(n 4k--lg k) algorithm for finding all minimum k-way cuts in graphs. Our algorithm is based on a divide-and-conquer method and improves all well-known existing algorithms along this divide-and-conquer method. As for approximation algorithms, we determine the tight approximation ratio of a general greedy splitting algorithm (finding a minimum k-way cut by iteratively increasing a constant number of components). Our result implies that the approximation ratio of the algorithm that iteratively increases h -- 1 components is 2 -- h/k + O(h2 /k2), which settles a well-known open problem. / For an unweighted graph and a given subset T ⊂ V of k terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of l edges (respectively, non-terminal vertices), whose removal from G separates each terminal from all the others. We show that Edge Multiterminal Cut is polynomial-time solvable for 1 = O(log n) by presenting an O(2lkT(n, m)) algorithm, where T(n, m) is the running time of finding a maximum flow in unweighted graphs. We also give three algorithms for Vertex Multiterminal Cut that run in O(k lT(n, m)), O( l!2 2l T(n, m)) and O(lk 4lT( n, m)) time respectively. Furthermore, we obtain faster algorithms for small k: Edge 3-Terminal Cut can be solved in O(1.415lT(n, m)) time, and Vertex {3, 4, 5, 6}-Terminal Cuts can be solved in O(2.059 lT(n, m)), O(2.772 lT(n, m)), O(3.349 lT(n, m)) and O(3.857 lT(n, m)) times respectively. Our results on Multiterminal Cut can be used to obtain faster algorithms for Multicut. / In this thesis, we study algorithmic issues for three closely related partition problems in graphs: k-Way Cut (k-Cut), Multiterminal Cut, and Multicut. These three problems attempt to separate a graph, by edge or vertex deletion, into several components with certain properties. The k-Way Cut (k-Cut) problem is to separate the graph into k components, the Multiterminal Cut problem is to separate a subset of vertices away from each other, and the Multicut problem is to separate some given pairs of vertices. These three problems have many applications in parallel and distributed computing, VLSI system design, clustering problems, communications network and many others. / Xiao, Mingyu. / Adviser: Andrew C. Yao. / Source: Dissertation Abstracts International, Volume: 70-06, Section: B, page: 3617. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 85-92). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in English and Chinese. / School code: 1307.

Thesis (M.Sc.)--York University, 2006. Graduate Programme in Mathematics and Statistics. / Typescript. Includes bibliographical references (leaves 168-173). Also available on the Internet. MODE OF ACCESS via web browser by entering the following URL: http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&res_dat=xri:pqdiss&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&rft_dat=xri:pqdiss:MR19755

Attributed Relational Graph (ARG) is a powerful representation for model based object recognition due to its inherent robustness in handling noisy and incomplete data. In the past few years, the availability of efficient ARG matching algorithms and their theoretical underpinnings have greatly contributed to many successful applications of ARG representation in tackling high level vision problems. During my past three year investigation into object recognition using ARG representation, we have developed a number of novel theories and techniques in the subject area. Some are image processing techniques which help to segment and generate primitive features for building ARG representation (Chapter 2 and 4). Some are about projective invariance in ARG representations (Chapter 3 and 5). Some are about new ARG matching algorithms (Chapter 6). This thesis serves as a summary document of these theories and techniques. The most important contributions of our work to the domain of computer vision, in my opinion, are in two areas: Firstly, in the area of projective invariant ARG representation for object recognition. Here, we demonstrated for the first time, a way to systematically derive ARG representation for objects under complex projective transform by exploiting the knowledge of invariance. The methodology developed by us is a sound strategy that generates ARG representations with a number of desirable and provable properties, amongst which, the most important one is the ability to capture global transformation constraint using binary relations only. The approach significantly reduces the heuristic nature of designing relational measurements and paves the way for wider application of ARG representation in 2D and 3D object recognition. Secondly, in the area of ARG matching. A new mathematical framework for deterministic relaxation algorithms was developed to overcome a number of problems appeared in the existing theories and practises of efficient ARG labelling. A novel labelling algorithm was proposed based on the new theoretical framework. The algorithm has a number of desirable properties compared to existing algorithms. In particular, the resulting algorithm delivers more consistent, faithful-to-observation results in the presence of ambiguities and multiple interpretations compared to other algorithms.

No description available.

Center location on cactus graphs. The p-center problem has been shown to be NP-hard for case of a general graph, yet polynomial algorithms exist for the case of a tree graph. Specifically, we consider "cactus graphs" where each edge is contained in at most one cycle. We show that the p-center problem on this class can be solved in polynomial time using a decomposition algorithm. We partition the graph into a set of subgraphs which are then solved sequentially. The solutions to the subgraphs are linked by a single parameter. The algorithm runs in polynomial time. Locating capacity limited centers on trees. The uncapacitated p-center problem on trees is solvable in polynomial time. We extend this result to include the case where each center can serve a limited number of customers and show that the capacitated p-center on trees can be solved in polynomial time when the capacities are identical. The algorithm consists of solving a capacitated covering problem and then using search routines to find the optimal domination radius. Center location on spheres. We discuss the unweighted center location problem. The following results are presented: (i) An O(n) time algorithm to solve the 1-center problem if the vertices are on one half of the sphere, and an O(n) time algorithm to check whether this condition holds. Both algorithms are based on presenting the problems as 3-dimensional convex programming problems with linear constraints and applying a pruning technique to find the optimum in O(n) time. (ii) An O(n$\sp3$ log n) time algorithm for the 2-center problem on the whole sphere. (iii) A reduction to show that the general p-center problem on a sphere is NP-hard. Locating hyperplanes on hypercubes. In linear regression models we are interested in locating a (d-1) dimensional hyperplane that will be as "close" as possible to existing vertices in the d-dimensional hypercube. The least squares criterion is usually applied for the linear fitting problem; while fitting according to the least absolute value ("minisum") seems to be "complicated". We solve fitting problems with the minisum criterion and present linear time algorithms when the dimension d is fixed. (Abstract shortened with permission of author.)

The prevalence of graphs in emerging applications has recently raised a lot of research interests. To acquire interesting information hidden in large graphs, tasks including link prediction, collaborative recommendation, and reputation ranking, all make use of proximities between graph nodes. The discounted hitting time (DHT), which is a random-walk similarity measure for graph node pairs, has shown to be useful in various applications. In this thesis, we examine a novel query, called the multi-way join (or n-way join), over DHT scores. Given a graph and n sets of nodes, the n-way join retrieves a ranked list of n-tuples with the k highest scores, according to some aggregation function of DHT values. By extracting such top-k results, this query enables the analysis and prediction of various complex relationships among n sets of nodes on a large graph. Since an n-way join is expensive to evaluate, we develop the Partial Join algorithm (or PJ). This solution decomposes an n-way join into a number of top-m 2-way joins, and combines their results to construct the answer of the n-way join. Since the process of PJ may necessitate the computation of top-(m + 1) 2-way joins, we study an incremental solution, which saves the trouble of recomputation and allows the results of top-(m+1) 2-way join to be derived quickly from the top-m 2-way join results earlier computed. For better performance, we further examine efficient processing algorithms and pruning techniques for 2-way joins. Through extensive experiments on three real graph datasets, we show that the proposed PJ algorithm accurately evaluates n-way joins, and is four orders of magnitude faster than basic solutions. / published_or_final_version / Computer Science / Master / Master of Philosophy

Thesis (Ph. D.)--Rutgers University, 2007. / "Graduate Program in Operations Research." Includes bibliographical references (p. 132-138).

Thesis (M.S.)--Ohio University, March, 2004. / Title from PDF t.p. Includes bibliographical references (leaves 51-55).

Thesis (Ph. D.)--University of Canterbury, 2008. / Typescript (photocopy). Includes bibliographical references (p. 119-144). Also available via the World Wide Web.

Thesis (Ph. D.)--Drexel University, 2005. / Includes abstract and vita. Includes bibliographical references (leaves 121-129).