Graph-Theoretic Concepts in Computer Science: 36th International Workshop, WG 2010, Zarós, Crete, Greece, June 28-30, 2010, Revised PapersDimitrios M. Thilikos The 36th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2010) took place in Zar ́ os, Crete, Greece, June 28-30, 2010. About 60 mathematicians and computer scientists from all over the world (Australia, Canada, Czech Republic, France, Germany, Greece, Hungary, Israel, Japan, The Netherlands, Norway, Poland, Switzerland, the UK, and the USA) attended the conference. WG has a long tradition. Since 1975, WG has taken place 21 times in Germany, four times in The Netherlands, twice in Austria, twice in France and once in the Czech Republic, Greece, Italy, Norway, Slovakia, Switzerland, and the UK. WG aims at merging theory and practice by demonstrating how concepts from graph theory can be applied to various areas in computer science, or by extracting new graph theoretic problems from applications. The goal is to presentemergingresearchresultsand to identify and exploredirections of future research.The conference is well-balanced with respect to established researchers and young scientists. There were 94 submissions, two of which where withdrawn before entering the review process. Each submission was carefully reviewed by at least 3, and on average 4.5, members of the Program Committee. The Committee accepted 28 papers, which makes an acceptance ratio of around 30%. I should stress that, due to the high competition and the limited schedule, there were papers that were not accepted while they deserved to be. |
Common terms and phrases
adjacent algorithm antipath arcs assume bipartite graphs bipartite permutation graph boolean-width Ccentre class of graphs clique clique-width color comparability graph connected component convex corresponding cutwidth decomposition define degree denote digraph directed path graphs Discrete disjoint DOMINATING SET endpoint Eulerian extension exists FEEDBACK VERTEX SET graph G independent set induced subgraph input integer interval graphs interval vertex deletion k-colorings lattice least Lemma Let G linear LNCS Math MAX-CUT maximum multigraph neighbors node NP-complete NP-hard number of edges obstacle number pair parameter parameterized complexity partition path graphs pathwidth permutation graphs planar graphs plane polynomial polynomial kernel polynomial-time position Proof prove q)-cluster graph random robots Section segment sequence small cycle solvable solved Springer stable allocation stable flow subset Theorem treewidth undirected unit disk graph unit interval unit interval vertex upper bound V₁ VERTEX COVER vertices of G