Graph Algorithm and Combinatorial Optimization

NII Shonan Meeting:

@ Shonan Village Center, Feb. 13-18, 2011

NII Shonan Meeting Report (ISSN 2186-7437):No. 2011-1


  • Satoru Iwata (RIMS, Kyoto University)
  • Ken-ichi Kawarabayashi (NII)


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.

NII Shonan Meeting Report (ISSN 2186-7437)

No. 2011-1


  1. Hello there, just became alert to your blog through Google, and found that it is truly informative. I’m going to watch out for brussels. I’ll be grateful if you continue this in future. A lot of people will be benefited from your writing. Cheers!

  2. This specific is an extremely wonderful web site you have visiting this site. The matter is very useful along with right to the issue. Psyched to learn more details on your blog next occasion.

  3. Hey there! Someone in my Facebook group shared this site with us so I came to take a look. I’m definitely loving the information. I’m book-marking and will be tweeting this to my followers! Outstanding blog and outstanding design.

  4. Life is just one prolonged means of strenious. Samuel Servant

  5. Thanks for your submission. I would also like to say that the first thing you will need to perform is determine whether you really need credit restoration. To do that you have got to get your hands on a replica of your credit rating. That should really not be difficult, ever since the government makes it necessary that you are allowed to acquire one free copy of your own credit report per year. You just have to request that from the right folks. You can either look at website for the Federal Trade Commission and also contact one of the main credit agencies instantly.