Dieter Kratsch - Böcker

This book constitutes the thoroughly refereed post-conference proceedings of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014, held in Nouan-le-Fuzelier, France, in June 2014.The 32 revised full papers presented were carefully reviewed and selected from 80 submissions. The book also includes two invited papers. The papers cover a wide range of topics in graph theory related to computer science, such as design and analysis of sequential, parallel, randomized, parameterized and distributed graph and network algorithms; structural graph theory with algorithmic or complexity applications; computational complexity of graph and network problems; graph grammars, graph rewriting systems and graph modeling; graph drawing and layouts; computational geometry; random graphs and models of the web and scale-free networks; and support of these concepts by suitable implementations and applications.

The 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005) was held on the campus "Ile du Saulcy" of the Univ- sity Paul Verlaine-Metz in France. The workshop was organized by the La- ratoire d'Informatique Th' eorique et Appliqu' ee (LITA) and it took place June 23 - 25 2005. The 94 participants of WG 2005 came from universities and - search institutes of 18 di?erent countries. The WG 2005 workshop continues the series of 30 previous WG workshops. Since 1975,WG has taken place 20 times in Germany, four times in The Neth- lands,twotimesinAustriaaswellasonceinItaly,inSlovakia,inSwitzerlandand inCzechRepublic, andhas nowbeen heldfor the ?rsttime inFrance.The wo- shop aims at uniting theory and practice by demonstrating how graph-theoretic concepts can be applied to various areas in computer science, or by extracting new problems from applications. The goal is to present recent research results and to identify and explore directions of future research. The talks were given in the "Petit Th' eatre".They showed how recent research results from algori- mic graph theory can be used in computer science and which graph-theoretic questions arise from new developments in computer science. There were two fascinating invited lectures by Georg Gottlob (Vienna, Austria) and Gregory Kucherov (Nancy, France).

The 33rd International Conference “Workshop on Graph-Theoretic Concepts in Computer Science” (WG 2007) took place in the Conference Center in old castleinDornburgnearJena,Germany,June21–23,2007.Theapproximately80 participants came from various countries all over the world, among them Brazil, Canada, the Czech Republic, France, UK, Greece, Hungary, Italy, Japan, The Netherlands, Norway, Sweden, Taiwan, and the USA. WG 2007 continued the series of 32 previous WG conferences. Since 1975, the WG conference has taken place 20 times in Germany, four times in The Netherlands, twice in Austria as well as once in Italy, Slovakia, Switzerland, the Czech Republic, France and in Norway. The WG conference traditionally aims at uniting theory and practice by demonstrating how graph-theoretic concepts can be applied to various areas in computer science, or by extracting new problems from applications. The goal is to present recent researchresults and to identify and exploredirections of future research. Thecontinuinginterestinthe WGconferenceswasre?ectedin thehighn- ber of submissions; 99 papers were submitted and in an evaluation process with four reports per submission, 30 papers were accepted by the Program Comm- tee for the conference. Due to the high number of submissions and the limited schedule of 3 days, various good papers could not be accepted. There were invited talks by Ming-Yang Kao (Evanston, Illinois) on algori- mic DNA assembly, and by Klaus Jansen (Kiel, Germany) on approximation algorithms for geometric intersection graphs.

For a long time computer scientists have distinguished between fast and slow algo rithms. Fast (or good) algorithms are the algorithms that run in polynomial time, which means that the number of steps required for the algorithm to solve a problem is bounded by some polynomial in the length of the input. All other algorithms are slow (or bad). The running time of slow algorithms is usually exponential. This book is about bad algorithms. There are several reasons why we are interested in exponential time algorithms. Most of us believe that there are many natural problems which cannot be solved by polynomial time algorithms. The most famous and oldest family of hard problems is the family of NP complete problems. Most likely there are no polynomial time al gorithms solving these hard problems and in the worst case scenario the exponential running time is unavoidable. Every combinatorial problem is solvable in ?nite time by enumerating all possi ble solutions, i. e. by brute force search. But is brute force search always unavoid able? De?nitely not. Already in the nineteen sixties and seventies it was known that some NP complete problems can be solved signi?cantly faster than by brute force search. Three classic examples are the following algorithms for the TRAVELLING SALESMAN problem, MAXIMUM INDEPENDENT SET, and COLORING.