We present an algorithm for finding a maximum weight independent set of a circle graph. For a cicle graph of a set of n chords with N endpoints, the algorithm finds a maximum weight independent set in O(nN) time and O(n) space.

Some properties π on graphs are characterized in terms of a set S(π) of forbidden graphs, that is, a graph G satisfies property π if and only if G has no subgraph homeomorphic (subcontraction isomorphic) to graph in S(π). Among such properties, πplanarity" is the most famous, where S(π){K3, 3, K5}. This paper clarifies the relations among such properties and presents necessary and sufficient conditions for a property to be characterizable in terms of k-connected (k1, 2, 3) forbidden graphs.

We present a simple approximation algorithm for a problem of partitioning a polygonal region into a minimum number of triangles. The objective is to show that the absolute performance ratio of the algorithm is bounded by some constant for any polygonal region.

The planar point location problem is one of the most fundamental problems in computational geometry and stated as follows： Given a straight line planar graph (subdivision) with n vertices and an arbitary query point Q, determine the region containing Q. Many algorithms have been proposed, and some of them are known to be theoretically optimal (O(log n) search time, O(n) space and O(n log n) preprocessing time). In this paper, we implement several representative algorithms in C, and investigate their practical efficiencies by computational experiments on Voronoi diagrams with 210 - 217 vertices.

We discuss Nash equilibria in combinatorial auctions with item bidding. Specifically, we give a characterization for the existence of a Nash equilibrium in a combinatorial auction with item bidding when valuations by n bidders satisfy symmetric and subadditive properties. By this characterization, we can obtain an algorithm for deciding whether a Nash equilibrium exists in such a combinatorial auction.

A sequence of nonnegative integers S=(s1, s2, , sn) is graphical if there is a graph with vertices v1,v2, ,vn such that deg(vi)=si for each i=1, 2, , n. The graphical degree sequence problem is： Given a sequence of nonnegative integers, determine whether it is graphical or not. In this paper, we consider several variations of the graphical degree sequence problem and give efficient algorithms.

For NP-hard combinatorial optimization problems, approximation algorithms with high performances have been proposed. In many of these algorithms, mathematical programming techniques have been used and proved to be very useful. In this survey, we present recent mathematical programming techniques as well as classic fundamental techniques, by showing how these techniques are used in designing high-quality approximation algorithms for NP-hard combinatorial optimization problems.