<< Chapter < Page Chapter >> Page >
This report summarizes work done as part of the Wavelet Based Image Analysis PFUG under Rice University's VIGRE program. VIGRE is a program of Vertically Integrated Grants for Research and Education in the Mathematical Sciences under the direction of the National Science Foundation. A PFUG is a group of Postdocs, Faculty, Undergraduates and Graduate students formed round the study of a common problem. This module provides mathematical background on the maxcut problem and develops an exact branch and bound algorithm for the maximum cut of unweighted graphs that is designed for improved performance on sparse graphs.

Introduction

Finding the maximum cut of a graph is a difficult to compute problem in combinatorial optimization with several applications in the world of engineering and physics. This research develops and evaluates an exact branch and bound algorithm for the maximum cut of unweighted graphs that is designed for improved performance on sparse graphs.

The module provides a general overview of the problem along with necessary mathematical background in "The Maxcut Problem" and a brief note on various approaches to the problem in "Several Algorithms" . "A New Algorithm" describes a new algorithm for finding maximum cuts. Results of empirical performance evaluation appear in "Empirical Testing" , which "Conclusion" further discusses.

The maxcut problem

Before discussing the maxcut problem, it is necessary to provide some background information regarding relevant concepts in graph theory, the most fundamental of which is the graph itself. A graph G ( V , E ) is an ordered pair comprised of a set of vertices V and a set of edges E that connect pairs of distinct vertices in V . Two examples are shown in [link] . Graphs may be either weighted, in which a real value is assigned to each edge, or unweighted, in which all edges have equal value. Although the former is more broadly applicable, further discussion will focus almost exclusively on the latter.

Two example graphs appear above.

Unsurprisingly, a subgraph G 1 ( V 1 , E 1 ) of graph G ( V , E ) is a graph with vertex set V 1 V and edge set E 1 E . Of particular usefulness will be the subgraph of G ( V , E ) induced by a given set of edges E 1 E , known as edge induced subgraph, which consists of that given set of edges E 1 along with all vertices V 1 = v | ( u , v ) E 1 , u V that occur as an endpoint of at least one edge in E 1 . An example of an edge induced subgraph is shown in [link] .

The subgraph induced by the red colored edges is shown on the right.

One class of graphs that will be especially important to discussion of the maxcut problem is bipartite graphs. A graph G ( V , E ) is bipartite, like the example in [link] , if there are sets V 1 , V 2 V such that V 1 V 2 = V , V 1 V 2 = , and ( u , v ) E only if u V 1 , v V 2 or v V 1 , u V 2 . Additionally, a graph is bipartite if and only if it has no subgraph that is a cycle of odd length.

In the above bipartite graph, the vertices are colored red or blue to highlight the vertex partitions.

A cut of a graph can be informally understood and visualized as a closed curve crossing some realization of the graph where each edge can be crossed at most once, as seen in [link] . Notice that the curve partitions the graph vertices into two disjoint subsets located to each side of the curve.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, The art of the pfug. OpenStax CNX. Jun 05, 2013 Download for free at http://cnx.org/content/col10523/1.34
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'The art of the pfug' conversation and receive update notifications?

Ask