<< Chapter < Page Chapter >> Page >

Several researchers have published algorithms that attempt to improve performance, especially focusing on sparse graphs. Notable approaches include those of Wheeler with O * ( 2 | V | ) [link] , Fedin and Kulikov with O * ( 2 | E | / 4 ) [link] , Croce, Kaminski, and Paschos with O * ( 2 | V | | E | / | V | + | E | ) , and Williams with O * ( 2 ω | V | / 3 ) , ω < 2 . 376 [link] . Although the last algorithm has the best computational complexity, it requires exponential space while the others require only polynomial bounded space. Due to limited memory storage capacity, algorithms requiring only polynomial bounded space are highly preferable.

A new algorithm

In attempt to improve performance for sparse graphs, this research presents a new exact algorithm for finding maximum cuts of unweighted graphs that will now be described. It requires polynomial bounded space and has computational complexity O ( | E | 2 | E | ) . The general approach that this algorithm takes is to separate the graph into its connected components and calculate initial upper and lower bounds for the maximum cut of each connected component. Those initial bounds are then used with a branch and bound algorithm to find a maximum cut of each connected component, and the maximum cuts of the connected components are be combined to find the maximum cut of the original graph.

In order to accomplish this, let I be the set of edge induced subgraphs of graph G ( V , E ) . Let E be indexed by Z [ 1 , | E | ] according to some ordering. Let I be indexed by Z [ 0 , 2 | E | - 1 ] according to the bijective function f : Z [ 0 , 2 | E | - 1 ] I such that

f - 1 ( G 1 ( V 1 , E 1 ) ) = i = 1 | E | 0 e i E 1 2 | E | - i e i E 1

This indexing provides the advantage that the size of each element is the number of zeros in the binary representation of the index. Thus, it enables the use of the edge and graph indices to rapidly eliminate subgraphs that cannot be bipartite and surpass the current lower bound for the maximum cut.

Within this framework, the algorithm searches for the lowest indexed element of I that is bipartite and larger than the current lower bound by iterating over the edges in order, adding each edge to the cut set if it passes a parity check and stopping when the final edge is reached or the number of edges not cut ensures the result will not exceed the lower bound. If such an element is found, the size of the graph is a new lower bound for the maximum cut, and the search continues by removing last cut edge with at least one vertex not colored by a lesser indexed edge before last two edges not in cut set. Continue iterating from that edge if such an edge is found, but terminate if no such edge exists or a cut equal to the upper bound is reached. Otherwise, the search ends and the final lower bound is the size of the maximum cut.

This process can be visualized as a directed graph, like those in [link] , [link] , and [link] , where each step represents a decision whether to include an edge in the cut set. A movement directly downward from a node indicates that the corresponding edge is not cut, while a movement diagonally downward indicates that the corresponding edge is cut. Each path from the top node to one of the bottom nodes corresponds to an edge induced subgraph of the graph being examined. The number of the final node reached (from left to right starting with 0) is the number of edges included. The algorithm seeks to find a path corresponding to a bipartite subgraph that leads farthest to the right. The red line to the left represents the lower bound, and all nodes below this line cannot be part of a path that leads farther right than the lower bound. The red line to the right represents the upper bound, and all nodes to the right of this line can only be a part of paths that exceed the upper bound. Therefore these regions need not be explored. An illustrative example, corresponding to an instance of K 4 with an edge ordering conductive to demonstration where a lower bound of 2 and an upper bound of 4 have been initially calculated (poor lower bound chosen for purpose of demonstration), is shown in [link] , [link] , and [link] .

This image illustrates the process for a K 4 (with poorly estimated lower bound for purposes of demonstration). Each step represents a decision on including the corresponding edge. Each path from top to bottom, like that in blue, corresponds to an edge induced subgraph. The red lines correspond to upper and lower bounds.
The algorithm searches for paths that lead further to the right than previously found. There is no need to search in regions beyond the red lines indicating bounds, which have been updated from the initial lower bound after finding a larger solution in the previous figure.
Finally, a solution leading further right is found. Because this solution is of equal size to the upper bound, the search ends since there cannot be a larger cut.

Empirical testing

This new algorithm was compared to the exhaustive algorithm for performance in empirical testing as shown in [link] . The image shows a plot of average runtime for graphs with | V | = 20 nodes and numbers of edges between 0 and 3 | V | = 60 . Each data point for each algorithm is the average of runtimes for five randomly generated graphs with the same number of vertices. In the testing, the new algorithm outperformed the exhaustive algorithm at low densities about until | E | < 2 . 5 | V | , successfully improving performance over the exhaustive algorithm at sufficiently low densities. However, no comparison to other algorithms developed by other researchers has been performed, and the algorithm is not expected to match or improve upon their performance.

This image shows a plot of average runtime for graphs with | V | = 20 nodes and numbers of edges between 0 and 3 | V | = 60 . Each data point for each algorithm is the average of runtimes for five randomly generated graphs with the same number of vertices.

Conclusion

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 was designed for improved performance on sparse graphs. Although the algorithm developed provides a performance improvement over the exhaustive algorithm, it is not expected to perform as well or better than other algorithms developed by other researchers. Thus, further improvement of the algorithm, focusing on investigating the effect of edge orderings on the performance of the algorithm and finding additional measures to reduce the number of edge induced subgraphs traversed by the algorithm, and more extensive empirical evaluation are necessary.

Questions & Answers

what is mutation
Janga Reply
what is a cell
Sifune Reply
how is urine form
Sifune
what is antagonism?
mahase Reply
classification of plants, gymnosperm features.
Linsy Reply
what is the features of gymnosperm
Linsy
how many types of solid did we have
Samuel Reply
what is an ionic bond
Samuel
What is Atoms
Daprince Reply
what is fallopian tube
Merolyn
what is bladder
Merolyn
what's bulbourethral gland
Eduek Reply
urine is formed in the nephron of the renal medulla in the kidney. It starts from filtration, then selective reabsorption and finally secretion
onuoha Reply
State the evolution relation and relevance between endoplasmic reticulum and cytoskeleton as it relates to cell.
Jeremiah
what is heart
Konadu Reply
how is urine formed in human
Konadu
how is urine formed in human
Rahma
what is the diference between a cavity and a canal
Pelagie Reply
what is the causative agent of malaria
Diamond
malaria is caused by an insect called mosquito.
Naomi
Malaria is cause by female anopheles mosquito
Isaac
Malaria is caused by plasmodium Female anopheles mosquitoe is d carrier
Olalekan
a canal is more needed in a root but a cavity is a bad effect
Commander
what are pathogens
Don Reply
In biology, a pathogen (Greek: πάθος pathos "suffering", "passion" and -γενής -genēs "producer of") in the oldest and broadest sense, is anything that can produce disease. A pathogen may also be referred to as an infectious agent, or simply a germ. The term pathogen came into use in the 1880s.[1][2
Zainab
A virus
Commander
Definition of respiration
Muhsin Reply
respiration is the process in which we breath in oxygen and breath out carbon dioxide
Achor
how are lungs work
Commander
where does digestion begins
Achiri Reply
in the mouth
EZEKIEL
what are the functions of follicle stimulating harmones?
Rashima Reply
stimulates the follicle to release the mature ovum into the oviduct
Davonte
what are the functions of Endocrine and pituitary gland
Chinaza
endocrine secrete hormone and regulate body process
Achor
while pituitary gland is an example of endocrine system and it's found in the Brain
Achor
what's biology?
Egbodo Reply
Biology is the study of living organisms, divided into many specialized field that cover their morphology, physiology,anatomy, behaviour,origin and distribution.
Lisah
biology is the study of life.
Alfreda
Biology is the study of how living organisms live and survive in a specific environment
Sifune
Got questions? Join the online conversation and get instant answers!
Jobilize.com Reply

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