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.)

No description available.

No description available.

Thesis (Ph.D.)--University of Nebraska-Lincoln, 2006. / Title from title screen (site viewed on Feb. 5, 2007). PDF text: 66 p. : ill. (some col.) UMI publication number: AAT 3216432. Includes bibliographical references. Also available in microfilm and microfiche format.

No description available.

Hajós conjectured that, for any positive integer k, every graph containing no K_(k+1)-subdivision is k-colorable. This is true when k is at most three, and false when k exceeds six. Hajós' conjecture remains open for k=4,5. We will first present some known results on Hajós' conjecture. Then we derive a result on the structure of 2-connected graphs with no cycle through three specified vertices. This result will then be used for the proof of the main result of this thesis. We show that any possible counterexample to Hajós' conjecture for k=4 with minimum number of vertices must be 4-connected. This is a step in an attempt to reduce Hajós' conjecture for k=4 to the conjecture of Seymour that any 5-connected non-planar graph contains a K_5-subdivision.

Thesis (M.S.)--West Virginia University, 2002. / Title from document title page. Document formatted into pages; contains iii, 19 p. Includes abstract. Includes bibliographical references (p. 17-19).

Thesis (Ph. D.)--West Virginia University, 2003. / Title from document title page. Document formatted into pages; contains vi, 52 p. : ill. Includes abstract. Includes bibliographical references (p. 50-52).

Given a finite set S of n nonintersecting line segments with no three end points collinear, the segment end point visibility graph is defined as the graph whose vertices are the end points of the line segments in S and two vertices are adjacent if the straight line segment joining two end points does not intersect any element of S, or if they are end points of the same segment. Segment end point visibility graphs have a wide variety of applications in VLSI circuit design, study of art gallery problems, and other areas of computational geometry. This thesis contains a survey of the important results that are currently known regarding the characterization of these graphs. Also a weak visibility dual of a segment end point visibility graph is defined and some structural properties of such graphs are presented. Some open problems and questions related to the characterization of weak visibility graphs are also discussed. / Department of Mathematical Sciences

Research Doctorate - Doctor of Philosophy (PhD) / There is a strong connection between directed graphs and the shifts of finite type which are an important family of dynamical systems. Higher-rank graphs (or k-graphs) and their C*-algebras were introduced by Kumjian and Pask to generalise directed graphs and their C*-algebras. Kumjian and Pask showed how higher-dimensional shifts of finite type can be associated to k-graphs, but did not discuss how one might associate k-graphs to k-dimensional shifts of finite type. In this thesis we construct a family of 2-graphs A arising from a certain type of algebraic two-dimensional shift of finite type studied by Schmidt, and analyse the structure of their C*-algebras. Graph algebras and k-graph algebras provide a rich source of examples for the classication of simple, purely infinite, nuclear C*-algebras. We give criteria which ensure that the C*-algebra C*(A) is simple, purely infinite, nuclear, and satisfies the hypotheses of the Kirchberg-Phillips Classification Theorem. We perform K-theory calculations for a wide range of our 2-graphs A using the Magma computational algebra system. The results of our calculations lead us to conjecture that the K-groups of C*(A) are finite cyclic groups of the same order. We are able to prove under mild hypotheses that the K-groups have the same order, but we have only numerical evidence to suggest that they are cyclic. In particular, we find several examples for which K1(C*(A)) is nonzero and has torsion, hence these are examples of 2-graph C*-algebras which do not arise as the C*-algebras of directed graphs. Finally, we consider a subfamily of 2-graphs with interesting combinatorial connections. We identify the nonsimple C*-algebras of these 2-graphs and calculate their K-theory.