Processing math: 100%
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at customercare@wspc.com for any enquiries.

SEARCH GUIDE  Download Search Tip PDF File

  • articleNo Access

    Succinct Data Structures for SP, Block-Cactus and 3-Leaf Power Graphs

    We design succinct encodings of series-parallel, block-cactus and 3-leaf power graphs while supporting the basic navigational queries such as degree, adjacency and neighborhood optimally in the RAM model with logarithmic word size. One salient feature of our representation is that it can achieve optimal space even though the exact space lower bound for these graph classes is not known. For these graph classes, we provide succinct data structures with optimal query support for the first time in the literature. For series-parallel multigraphs, our work also extends the works of Uno et al. (Disc. Math. Alg. and Appl., 2013) and Blelloch and Farzan (CPM, 2010) to produce optimal bounds.

  • articleNo Access

    BIPARTITIONING INTO OVERLAPPING SETS

    We consider a generalization of the min-cut partitioning problem where we partition a graph G=(V,E) into two sets V1 and V2 such that |V1∩V2|≤d, d<|V|, and such that |{(u, v)|u∈V1−V2, v∈V2−V1}| is minimized. The problem is trivially solvable using flow techniques for any fixed d, but we show that it is NP-hard for integer values of d. It remains NP-hard if we impose restrictions on the size of V1, i.e., |V1|=k, k∈Z+. The latter problem variation may apply in VLSI layout and hypertext partitioning. We present polynomial time algorithms for the special cases of solid grids and series-parallel graphs. Series-parallel graphs find applications in hypertext partitioning whereas grid graphs model the mapping of a class of Partial Differential Equation computations into parallel machines.

  • articleNo Access

    MATCHING POLYNOMIALS OF SERIES-PARALLEL GRAPHS

    We present an efficient algorithm for computing the matching polynomial of a series-parallel graph in O(n2) time. This algorithm improves on the previous result of O(n3). We also present a cost-optimal parallel algorithm for computing the matching polynomial of a series-parallel graph using an EREW PRAM computer with the number of processors p less than n2/ log n.

  • articleNo Access

    THE PROBLEM OF PARTITIONING WITH DUPLICATIONS AND ITS APPLICATIONS

    The problem of partitioning the elements of a graph G=(V, E) into two equal size sets A and B that share at most d elements such that the total number of edges (u, v), u∈A−B, v∈B−A is minimized, arises in the areas of Hypermedia Organization, Network Integrity, and VLSI Layout. We formulate the problem in terms of element duplication, where each element c∈A∩B is substituted by two copies c′∈A and c″∈B As a result, edges incident to c′ or c″ need not count in the cost of the partition. We show that this partitioning problem is NP-hard in general, and we present a solution which utilizes an optimal polynomial time algorithm for the special case where G is a series-parallel graph. We also discuss special other cases where the partitioning problem or variations are polynomially solvable.