Graph Optimization I
Date/Time: Sunday 13:00-14:30
Room: Crystal Parlor C
Chair: Mark E. Hartmann
Chair Address: Univ. of NC, Dept. of OR, 210 Smith Bldg., CB 3180, Chapel Hill, NC 27599-3180,
Finding K-tree Subgraphs Elham Ghashghai, Ron Rardin --- Purdue Univ., W Lafayette, IN 47906 , (email@example.com)
- 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...
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 , (firstname.lastname@example.org 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.
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 (email@example.com)
- 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.
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, (firstname.lastname@example.org)
- 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.