Narrow Results

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.

We consider a generalization of the min-cut partitioning problem where we partition a graph G=(V,E) into two sets V₁ and V₂ such that |V₁∩V₂|≤d, d<|V|, and such that |{(u, v)|u∈V₁−V₂, v∈V₂−V₁}| 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 V₁, i.e., |V₁|=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.

We present an efficient algorithm for computing the matching polynomial of a series-parallel graph in O(n²) time. This algorithm improves on the previous result of O(n³). 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 n²/ log n.