Structures that can be represented as graphs are ubiquitous, and many practical problems can be represented by graphs. The link structure of a web in Internet could be represented by a directed graph: the vertices are the web pages available at the website and a directed edge from page A to page B exists if and only if A contains a link to B. A graph structure can be extended by assigning a weight to each edge of the graph.

Networks have also many uses in the practical side of graph theory, network analysis (for example, to model and analyze traffic networks). Within network analysis, the definition of the term “network” varies, and may often refer to a simple graph.

A similar approach can be taken to problems in travel, biology, computer chip design, and many other fields. Development of algorithms to handle graphs is therefore of major interest in computer science.

These applications of graphs often gives rise to optimization. Basic optimization problems on graphs, including the shortest path, maximum flow, minimum spanning tree problems allow efficient exact algorithms. The algorithmic developments of these problems have led to the theory of combinatorial optimization, combined with polyhedral combinatorics, matroids and submodular functions.

On the other hand, most practical optimization problem on graphs such as the traveling salesman, stable set, maximum cut problems are NP-hard. Approximation algorithms for these NP-hard combinatorial optimization problems have been investigated extensively for a couple of decades. Design of approximation algorithms often requires deep insights from structural graph theory and polyhedral combinatorics.

The purpose of this workshop is to bring experts in graph algorithm and combinatorial optimization to share ideas, and to stimulate joint projects.