Graph Optimization I

SC06.1 Finding K-tree Subgraphs Elham Ghashghai, Ron Rardin --- Purdue Univ., W Lafayette, IN 47906 , (ghashgha@ecn.purdue.edu)

A k-tree is a graph that can be reduced to the k-clique by¨ repeatedly removing degree k vertices with completely connected¨ neighbors. We present a heuristic to identify a 'good' k-tree¨ subgraph of a complete graph. The optimal solution on this subgraph¨ is an approximation of the optimal solution on the complete graph.¨ This problem is motivated by the existence of many polynomial time¨ algorithms...

SC06.2 Maximum vs. Maximal Planar Subgraphs as Tool for Approximating the Thickness of a Graph Thomas Odenthal, Petra Mutzel, Mark Scharbrodt --- Columbia Univ., IEOR Dept., 331 Mudd, New York, NY 10027 , (odenthal@ieor.columbia edu)

The thickness of a graph is the minimum number of planar subgraphs¨ whose union is the original graph. It has applications in the¨ layout of printed circuits. We report on using maximum vs. maximal¨ planar subgraphs in a heuristic for approximating the thickness.¨ Further refinements of the heuristic are discussed.

SC06.3 The Construction of Alpha-Valuation of 2-Regular Graph with Three Components Consisting of Two Isomorphic Components Kourosh Eshghi, Jaromir V. Abrham --- Univ. of Toronto, Dept. of IE, 4 Taddlecreek Rd., Toronto, Ontario, , Canada M5S 3G8 (kourosh@ie.utoronto.ca)

We show that the Rosa's condition is sufficient for 2-regular graph¨ with 3 components consisting of 2 isomorphic components by covering¨ all special cases requiring different constructions of the¨ alpha-valuation of the graph under consideration.

SC06.4 Long Walks, Dynamic Programming & the Max-Algebra Mark E. Hartmann --- Univ. of NC, Dept. of OR, 210 Smith Bldg., CB 3180, Chapel Hill, NC 27599-3180, (mudville@or.unc.edu)

Maximum reward walks of a given length arise in discrete dynamic¨ programming and recursive systems in the max-algebra; their¨ structure yields 'almost' stationary optimal policies, an improved¨ bound on the transient via max-balancing the rewards and strongly¨ polynomial algorithms for solving these problems.