Taglio massimo su grafi cubici

We consider 1) the problem of finding in parallel a Maximum Bipartite Subgraph of a cubic graph G(V,E), that is known to be NP-complete even if the graph is triangle-free. We approach the problem as a Max Cut one. We analyze the solution structure according to the degree of vertices in the bipartition and to the odd girth g of the graph, showing that the number of edges in the bipartite subgraph is at least {{9g-3} / {8g}}|V|. The result of a wide experimentation rounds off the resulting paper (Calamoneri T., Finocchi I., Manoussakis Y e Petreschi R. Parallel Generation of Large Bipartite Subgraphs on Cubic Graphs , Proceedings of WAIT’99, pp.175 – 185, Buenos Aires - Argentina 1999) 2)We deal with the maximum cut problem in parallel for cubic graphs. Namely, we present new theoretical results characterizing the cardinality of the cut. These results make it possible to design a simple O(log n) time parallel algorithm, running on a CRCW P-RAM with O(n) processors. The approximation ratio of our algorithm is 1.3 and improves the best known parallel approximation ratio, i.e. 2, in the special case of cubic graphs. Moreover, we are able to guarantee that the size of the found cut is at least {9g-3}/{8g}n, where g is the odd girth of the input graph. The results of a wide experimentation round off the corresponding paper( Calamoneri T., Finocchi I., Manoussakis Y e Petreschi R., A Parallel Approximation Algorithm for the Max Cut Problem on Cubic Graphs, Proceedings of ASIAN’99, LNCS 1742, pp. 27 – 37, Phuket 1999 – Thailand 1999 and A Parallel Approximation Algorithm for the Max Cut Problem on Cubic Graphs, Journal on Parallel Algorithms and Applications, 17(3), pp. 165-183, 2001.)