skip to main content
Idioma:
Primo Search
Clear Search Box
Search in: Busca Geral
Busca Avançada
Busca por Índices

A Simple and fast approach for solving problems on planar graphs

Fomin, Fedor V ; Thilikos Touloupas, Dimitrios

2003

Texto completo disponível

Citações Citado por
  • Título:
    A Simple and fast approach for solving problems on planar graphs
  • Autor: Fomin, Fedor V ; Thilikos Touloupas, Dimitrios
  • Assuntos: Infografia ; Informàtica ; Lipton-Tarjan planar separation theorem ; Planar graph problems ; Àrees temàtiques de la UPC
  • Descrição: It is well known that the celebrated Lipton-Tarjan planar separation theorem, in a combination with a divide-and-conquer strategy leads to many complexity results for planar graph problems. For example, by using this approach, many planar graph problems can be solved in time 2^{O(sqrt{n})}, where n is the number of vertices. However, the constants hidden in big-Oh, usually are too large to claim the algorithms to be practical even on graphs of moderate size. Here we introduce a new algorithm design paradigm for solving problems on planar graphs. The paradigm is so simple that it can be explained in any textbook on graph algorithms: Compute tree or branch decomposition of a planar graph and do dynamic programming. Surprisingly such a simple approach provides faster algorithms for many problems. For example, Independent Set on planar graphs can be solved in time O(2^{3.182sqrt{n}}n+n^4) and Dominating Set in time O(2^{5.043sqrt{n}}n+n^4). In addition, significantly broader class of problems can be attacked by this method. Thus with our approach, Longest cycle on planar graphs is solved in time O(2^{2.29sqrt{n}(ln{n}+0.94)}n^{5/4}+n^4) and Bisection is solved in time O(2^{3.182sqrt{n}}n+n^4). The proof of these results is based on complicated combinatorial arguments that make strong use of results derived by the Graph Minors Theory. In particular we prove that branch-width of a planar graph is at most 2.122sqrt{n}. In addition we observe how a similar approach can be used for solving different fixed parameter problems on planar graphs. We prove that our method provides the best so far exponential speed-up for fundamental problems on planar graphs like Vertex Cover, (Weighted) Dominating Set, and many others.
  • Data de criação/publicação: 2003
  • Idioma: Inglês
Links
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.