VTechWorks staff will be away for the Thanksgiving holiday beginning at noon on Wednesday, November 27, through Friday, November 29. We will resume normal operations on Monday, December 2. Thank you for your patience.

Browsing by Author "Pemmaraju, Sriram V."

Now showing 1 - 7 of 7
  • Thumbnail Image
    Analysis of the Worst Case Space Complexity of a PR Quadtree
    Pemmaraju, Sriram V.; Shaffer, Clifford A. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1992)
    We demonstrate that a resolution-r PR quadtree containing n points has, in the worst case, at most nodes. This captures the fact that as n tends towards 4r, the number of nodes in a PR quadtree quickly approaches O(n). This is a more precise estimation of the worst case space requirement of a PR quadtree than has been attempted before.
  • Thumbnail Image
    Exploring the powers of stacks and queues via graph layouts
    Pemmaraju, Sriram V. (Virginia Tech, 1992)
    In this dissertation we employ stack and queue layouts of graphs to explore the relative power of stacks and queues. Stack layout and queue layouts of graphs can be examined from several points of view. A stack or a queue layout of a graph can be thought of as an embedding of the graph in a plane satisfying certain constraints, or as a graph linearization that optimizes certain cost measures, or as a scheme to process the edges of the graph using the fewest number of stacks or queues. All three points of view permeate this research, though the third point of view dominates. Specific problems in stack and queue layouts of graphs have their origin in the areas of VLSI, fault-tolerant computing, scheduling parallel processes, sorting with a network of stacks and queues, and matrix computations. We first present two tools that are useful in the combinatorial and algorithmic analysis of stack and queue layouts as well as in determining bounds on the stacknumber and the queuenumber for a variety of graphs. The first tool is a formulation of a queue layout of a graph as a covering of its adjacent matrix with staircases. Not only does this formulation serve as a tool for analyzing stack and queue layouts, it also leads to efficient algorithms for several problems related to sequences, graph theory, and computational geometry. The connection between queue layouts and matrix covers also forms the basis of a new scheme for performing matrix computations on a data driven network. Our analysis reveals that this scheme uses less hardware and is faster than existing schemes. The second tool is obtained by considering separated and mingled layouts of graphs. This tool allows us to obtain lower bounds on the stacknumber and the queuenumber of a graph by partitioning the graph into subgraphs and simply concentrating on the interaction of the subgraphs. These tools are used to obtain results in three areas. The first area is stack and queue layouts of directed acyclic graphs (dags). This area is motivated by problems of scheduling parallel processes. We establish the stacknumber and the queuenumber of classes of dags such as trees, unicylic graphs, outerplanar graphs, and planar graphs. We then present linear time algorithms to recognize 1-stack dags and leveled-planar dags. In contrast, we show that the problem of recognizing 9-stack dags and the problem of recognizing 4-queue dags are both NP-complete. The second area is stack and queue layouts of partially ordered sets (posets). We establish upper bounds on the queuenumber of a poset in terms of other measures such as length, width, and jumpnumber. We also present lower bounds on the stacknumber and on the queuenumber of certain classes of posets. We conclude by showing that the problem of recognizing a 4-queue poset is NP-complete. The third area is queue layouts of planar graphs. While it has been shown that the stacknumber of the family of planar graphs is 4, the queuenumber of planar graphs is unknown. We conjecture that a family of planar graphs—the stellated triangles—has unbounded queuenumber; using separated and mingled layouts, we demonstrate significant progress towards that result.
  • Thumbnail Image
    Modal logics of provability
    Pemmaraju, Sriram V. (Virginia Tech, 1989-05-05)
    Gödel proved his Incompleteness theorems for any theory 'strong' enough to represent recursive functions. In the process he showed that the provability predicate can be represented in such theories. Modal logics of provability are modal logics which attempt to express the concept of 'provability' and 'consistency' using the modal operators '[]' and '<>' respectively. This is achieved by forcing '[]' to behave like the provability predicate. GL is a modal logic which has been shown to be complete and sound with respect to arithmetic theories (theories which can represent all recursive functions), hence results about concepts such as 'consistency,' 'provability' and 'decidability' in arithmetic theories can be stated and proved in GL. It has also been proved that GL is complete with respect to the class of finite, transitive, reversely well-founded models. This essentially means that the set of theorems of GL is recursive and hence there exists an effective procedure to determine whether a given wff is a theorem of GL or not. We investigate a weaker version of GL called GH and show that GH is not complete with respect to arithmetic theories. We show this by first showing that GH is a proper subset of GL and then showing that the theorems missing from GH are properties of the provability predicate. We finally, show that GH is not complete with respect to the class of transitive, reversely well-founded models and hence not sound and complete with respect to any frame.
  • Thumbnail Image
    New Results for the Minimum Weight Triangulation Problem
    Heath, Lenwood S.; Pemmaraju, Sriram V. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1990)
    Given a finite set of points in a plane, a triangulation is a maximal set of non-intersecting line segments connecting the points. The weight of a triangulation is the sum of the Euclidean lengths of its line segments. Given a set of points in a plane, the minimum weight triangulation problem is to find a triangulation whose weight is minimal. No polynomial time algorithm is known to solve this problem, and it is unknown whether the problem is NP-hard. The current best polynomial time approximation algorithm produces a triangulation that can be 0(log n) times the weight of the optimal triangulation. We propose an algorithm that triangulates a set P, of n points in a plane in 0(n-cubed) time and that never does worse than the greedy triangulation. The algorithm produces an optimal triangulation if the points P are the vertices of a convex polygon. The algorithm has the flavor of a heuristic proposed by Lingas and analysis similar to his can be performed for our algorithm also, but experimental results indicate that our algorithm performs much better than the heuristic of Lingas. The results comparing the optimal triangulation with the performance of our algorithm, the heuristic of Lingas, and the greedy algorithm are within 0(1) of an optimal triangulation. We investigate issues of local optimality pertaining to known triangulation algorithms. We define the notion of k-optimality which suggests an interesting new approach to studying triangulation algorithms. We restate the minimum weight triangulation problem as a graph problem and show that NP-hardness of a closely related graph problem. Finally, we show that the constrained problem of computing the minimum weight of triangulation, given a set of points in a plane and enough edges to form a triangulation, is NP-hard. These results are an advance towards a proof that the minimum weight triangulation problem is NP-hard.
  • Thumbnail Image
    New Results for the Minimum Weight Triangulation Problem
    Heath, Lenwood S.; Pemmaraju, Sriram V. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1992)
    The current best polynomial time approximation algorithm produces a triangulation that can be O(log n) times the weight of the optimal triangulation. We propose an algorithm that triangulates a set P of n points in a plane in O(n3) time and that never does worse than the greedy triangulation. We investigate issues of local optimality pertaining to known triangulation algorithms and suggest an interesting new approach to studying triangulation algorithms. We restate the minimum weight triangulation problem as a graph problem and show the NP-hardness of a closely related graph problem. Finally, we show that the constrained problem of computing the minimum weight triangulation, given a set of points in a plane and enough edges to form a triangulation, is NP-hard. These results are an advance towards a proof that the minimum weight triangulation problem is NP-hard.
  • Queue Layouts and Staircase Covers of Matrices
    Abrams, Marc; Batongbacal, Alan; Ribler, Randy; Vazirani, Devendra; Heath, Lenwood S.; Pemmaraju, Sriram V. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1994-06-01)
    A connection between a queue layout of an undirected graph and a staircase cover of its adjacency matrix is established. The connection is exploited to establish a number of combinatorial results relating the number of vertices, the number of edges, and the queue number of a queue layout. The staircase notion is generalized to that of an (h,w)- staircase, and an efficient algorithm to optimally cover a matrix with (h,w)- staircases is presented. The algorithm is applied to problems of monotonic subsequences and to the maxdominance problem of Atallah and Kosaraju.
  • Thumbnail Image
    Stack and Queue Layouts of Posets
    Heath, Lenwood S.; Pemmaraju, Sriram V. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1992)
    The stacknumber (queuenumber) of a poset is defined as the stacknumber (queuenumber) of its Hasse diagram viewed as a directed acyclic graph. Upper bounds on the queuenumber of a poset are derived in terms of its jumpnumber, its length, its width, and the queuenumber of its covering graph. A lower bound of is shown for the queuenumber of the class of planar posets. The queuenumber of a planar poset is shown to be within a small constant factor of its width. The stacknumber of posets with planar covering graphs is shown to be . These results exhibit sharp differences between the stacknumber and queuenumber of posets as well as between the stacknumber (queuenumber) of a poset and the stacknumber (queuenumber) of its covering graph.