|
One-Day Conference “Graph Structure and Algorithms” Wednesday 2 June, 2010
A One-Day Conference “Graph Structure and Algorithms”
will be held at the School of Computing (RAF), Union University on
Wednesday 2 June 2010.
Schedule All talks will be held at Josif Pančić hall, Kolarac, Studentski trg 5
9:30 Kristina Vušković (RAF) The power of decomposition 10:30 coffee 10:45 Nicolas Trotignon (LIAFA) New structural results for chordal graphs 11:45 Pierre Charbit (LIAFA) Fast decomposition of graphs 12:45 lunch break 2:30 Michel Habib (LIAFA) Decompostion of graphs with 2-joints and applications 3:30 coffee 3:45 Marko Radovanović (RAF) 3-Coloring a class of triangle-free graphs 4:15 Igor Kabiljo (RAF) Use of graph theory in Wowd distributed search engine
Abstracts Kristina Vušković: The power of decomposition Abstract: The power of decomposition is that it allows us to understand complex structures by breaking them down into simpler ones. Once these simpler structures are understood, this knowledge is propagated back to the original structure by understanding how their composition behaves. The use of decomposition in combinatorial theory had great success in solving some of the difficult problems such as obtaining polynomial time recognition algorithms for regular matroids, balanced matrices, perfect graphs, even-hole-free graphs, proving the famous Strong Perfect Graph Conjecture, as well as for obtaining combinatorial algorithms for some optimization problems for subclasses of graphs closed under taking induced subgraphs. In this talk we survey all these results, with the focus on the use and development of the decomposition techniques in the context of classes of graphs closed under taking induced subgraphs. The key distinguishing property of graph classes closed under taking induced subgraphs as opposed to for example being closed under minor taking (i.e. closed under deleting and contracting edges) is the need to use strong cutsets for their decomposition. This is what makes it very difficult to use such decomposition theorems for constructing algorithms and obtaining other interesting properties.
Nicolas Trotignon: Decomposition of graphs with 2-joins and applications Abstract: 2-Joins are edge cutsets that naturally appear in the decomposition of several key classes of graphs closed under taking induced subgraphs, such as balanced bipartite graphs, even-hole-free graphs, perfect graphs and claw-free graphs. We will survey several such decomposition theorems. We will show that computing a maximum stable set by using 2-join decomposition is NP-hard in general. We will present a method to compute a maximum stable set and a maximum clique using 2-joins for a class perfect graphs. A consequence is a coloring algorithm for this class. These results were obtained joinly with K. Vušković.
Pierre Charbit: Fast decomposition of graphs Abstract: When dealing with applied algorithms the natural “divide and conquer” idea of breaking a graph into smaller pieces is often effective. Another interesting aspect that arose in the last twenty or so years is the applications of graph decomposition to purely theoretical results. This was for example at the core of the proof of the celebrated Strong Perfect Graph Theorem by Chudnovsky et al. The general idea is the following: if one wants to prove that a class of graphs C is included in another class D (which is somehow what every theorem says), one can prove that every graph in C is either a “simple” graph (that is easily shown to be in D) or it can be “broken” in a prescribed manner into smaller pieces, such that if these peaces are in D then so is the original graph. Among the decompositions that appeared naturally in the past decades are the joins that are particular types of edge cutsets. In this talk we will expose algorithmic results concerning 1-join decomposition (joint work with de Montgolfier and Raffinot) and 2-join decomposition (joint work with Habib, Trotignon and Vušković).
Michel Habib: New structural results for chordal graphs Abstract: Chordal graphs are one of the most studied classes of graphs and have many applications, as for example in bioinformatics to construct perfect phylogeny. It is well known that chordal graphs are exactly the intersection graphs of subtrees in a tree (Gavril 1974). We propose to further study the relationship between maximal cliques and minimal separators, by introducing a new structure called “the reduced clique graph” which contains all the information needed to build maximal cliques trees, standard representation of chordal graphs (such maximal clique trees provide representations using subtrees in a tree). We first prove a general decomposition of chordal graphs using split minors and then propose a polynomial algorithm to solve the leafage problem. For a chordal graph G, its leafage l(G) is the minimum number of leaves of a maximal clique tree of G (as defined by Lin, McKee and West 1998). Linear time algorithms are known for the particular case l(G)=2 (equivalent to recognition of interval graph, Boot and Lueker 1976) and a polynomial algorithm was also known for l(G)=3 (Prisner 1992). This is joint work with Juraj Stacho.
Marko Radovanović: 3-Coloring a class of triangle-free graphs Abstract: It is a well known fact that triangle-free graphs can have arbitrarily large chromatic number (i.e. the minimum number of colors needed to color vertices of a graph so that no two adjacent vertices receive the same color). The coloring problems remains difficult even when seemingly a lot of structure is imposed on a triangle-free graph. For example determining whether a graph is 3-colorable remains NP-complete for triangle-free graphs with maximum degree 4. A 3-path configuration 3PC(.,.) is a graph composed of three paths with common endnodes such that the union of any two of them induces a chordless cycle of length at least 4. In this talk we present a result (obtained in joint work with Vušković) that shows that graphs that do not contain as induced subgraphs triangles and 3PC(.,.)’s have the chromatic number bounded by 3. This result is obtained through the decomposition method and leads to an efficient coloring algorithm for this class.
Igor Kabiljo: Use of graph theory in Wowd distributed search engine Abstract: Wowd is a real-time „interest engine“ for search and discovery. Wowd is founded by Boris Agapiev in 2006, to address multiple centralized bottlenecks of Google (indexing, crawling, ranking) and real-time nature of the web. Development team is completely in Serbia, with most of the developers being students at RAF, and it is funded by venture capital firms from USA. Attention frontier – what people are looking at on the internet right now – is gathered, mined and indexed in real-time. Fully distributed index makes it all possible. Many specialized algorithms were developed or used for acheaving speed, reliability, quality and other goals. Partticularly, need for handling huge graphs appears in few places. For connecting all nodes, in a way to achieve minimal latency and maximal reliability, algorithm for construction of dynamic routable graph with minimal diameter is developed. For ranking of a few different graph structures, well known algorithm, PageRank, is improved to give superior performance.
|