Expected complexity of graph partitioning problems

Expected complexity of graph partitioning problems

0.00 Avg rating0 Votes
Article ID: iaor1997989
Country: Netherlands
Volume: 57
Issue: 2/3
Start Page Number: 193
End Page Number: 212
Publication Date: Feb 1995
Journal: Discrete Applied Mathematics
Authors:
Keywords: computational analysis
Abstract:

The paper studies the expected time complexity of two graph partitioning problems: the graph coloring and the cut into equal parts. If equ1, it can test whether two vertices of a k-colorable graph can be k-colored by the same color in time equ2 per of vertices with equ3-time preprocessing in such a way that for almost all k-colorable graphs the answer is correct for all pairs of vertices. From this the paper obtains a sublinear (with respect to the number of edges) expected time algorithm for k-coloring of k-colorable graphs (assuming the uniform input distribution). Similarly, if equ4 is a constant, and G is a graph having a cut of the vertex set into two equal parts with at most c cross-edges, it can test whether two vertices belong to the same class of some c-cut in time equ5 per vertex with equ6-time preprocessing in such a way that for almost all graphs having a c-cut the answer is correct for all pairs of vertices. The methods presented in the paper can also be used for other graph partitioning problems, e.g. the largest clique or independent subset.

Reviews

Required fields are marked *. Your email address will not be published.