Tratabilidade por Parâmetro Fixo para Largura em Árvore de Grafos Direcionados
Resumo
A largura em árvore de um grafo não-direcionado G é uma medida de quão similar G é de uma árvore. Uma definição análoga também é conhecida para grafos direcionados. Para k constante, nós melhoramos um resultado conhecido mostrando um algoritmo FPT, com parâmetro k, que decide se a largura em árvore de um grafo direcionado D é no máximo 3k − 2 ou se D admite um refúgio de ordem k.
Referências
Chen, J., Liu, Y., and Lu, S. (2007). Directed feedback vertex set problem is fpt. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs, number 07281 in Dagstuhl Seminar Proceedings. Internationales Begegnungsund Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany.
Chitnis, R., Hajiaghayi, M., and Marx, D. (2011). Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. abs/1110.0259.
Cook, W. and Seymour, P. (2003). Tour merging via branch-decompositions. J. on Computing, 15:233–248.
Courcelle, B. (1990). The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Information and Computation, 85(1):12 – 75.
Demaine, D., Fomin, V., Hajiaghayi, M., and Thilikos, M. (2005). Subexponential parameterized algorithms on bounded-genus graphs and h-minor-free graphs. J. ACM, 52(6):866–893.
Demaine, E. and Hajiaghayi, M. (2004). Fast algorithms for hard graph problems: Bidimensionality, minors, and local treewidth. Graph drawing, pages 517–533.
Erbacher, R., Jaeger, T., Talele, N., and Teutsch, J. (2014). Directed multicut with linearly ordered terminals. CoRR, abs/1407.7498.
Fomin, F., Lokshtanov, D., Raman, V., and Surabh, S. (2011). Bidimensionality and eptas. ACM-SIAM Symposium on discrete algorithms (SODA), pages 748–759.
Fomin, F., Lokshtanov, D., Surabh, S., and Thilikos, D. (2010). Bidimensionality and kernels. ACM-SIAM Symposium on discrete algorithms (SODA), pages 503–510.
Johnson, T., Robertson, N., Seymour, P., and Thomas, R. (2001). Directed tree-width. Journal of combinatorial theory, series B, 82(01):138–154.
Kawarabayashi, K. and Kreutzer, S. (2015). The directed grid theorem. In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC ’15, pages 655–664, New York, NY, USA. ACM.
Koster, A., van Hoesel, S., and Kolen, A. (1999). Solving frequency assignment problems via tree-decomposition. Broersma, H.J. et al 6th Twente workshop on graphs and combinatorial optimization. Univ. of Twente, Enschede, Netherlands, 3.
Reed, B. (1997). Tree width and tangles: A new connectivity measure and some applications. R. Bailey, editor, Surveys in Combinatorics, pages 87–162.
Reed, B. (1999). Introducing directed tree-width. Electronic notes in discrete mathematics, 03:222–229.
Robertson, N. and Seymour, P. (1986). Graph minors v. excluding a planar graph. Journal of combinatorial theory, series B, 41(01):92–114.
Chitnis, R., Hajiaghayi, M., and Marx, D. (2011). Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. abs/1110.0259.
Cook, W. and Seymour, P. (2003). Tour merging via branch-decompositions. J. on Computing, 15:233–248.
Courcelle, B. (1990). The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Information and Computation, 85(1):12 – 75.
Demaine, D., Fomin, V., Hajiaghayi, M., and Thilikos, M. (2005). Subexponential parameterized algorithms on bounded-genus graphs and h-minor-free graphs. J. ACM, 52(6):866–893.
Demaine, E. and Hajiaghayi, M. (2004). Fast algorithms for hard graph problems: Bidimensionality, minors, and local treewidth. Graph drawing, pages 517–533.
Erbacher, R., Jaeger, T., Talele, N., and Teutsch, J. (2014). Directed multicut with linearly ordered terminals. CoRR, abs/1407.7498.
Fomin, F., Lokshtanov, D., Raman, V., and Surabh, S. (2011). Bidimensionality and eptas. ACM-SIAM Symposium on discrete algorithms (SODA), pages 748–759.
Fomin, F., Lokshtanov, D., Surabh, S., and Thilikos, D. (2010). Bidimensionality and kernels. ACM-SIAM Symposium on discrete algorithms (SODA), pages 503–510.
Johnson, T., Robertson, N., Seymour, P., and Thomas, R. (2001). Directed tree-width. Journal of combinatorial theory, series B, 82(01):138–154.
Kawarabayashi, K. and Kreutzer, S. (2015). The directed grid theorem. In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC ’15, pages 655–664, New York, NY, USA. ACM.
Koster, A., van Hoesel, S., and Kolen, A. (1999). Solving frequency assignment problems via tree-decomposition. Broersma, H.J. et al 6th Twente workshop on graphs and combinatorial optimization. Univ. of Twente, Enschede, Netherlands, 3.
Reed, B. (1997). Tree width and tangles: A new connectivity measure and some applications. R. Bailey, editor, Surveys in Combinatorics, pages 87–162.
Reed, B. (1999). Introducing directed tree-width. Electronic notes in discrete mathematics, 03:222–229.
Robertson, N. and Seymour, P. (1986). Graph minors v. excluding a planar graph. Journal of combinatorial theory, series B, 41(01):92–114.
Publicado
26/07/2018
Como Citar
MAIA, A. Karolinna; LOPES, Raul; CAMPOS, Victor.
Tratabilidade por Parâmetro Fixo para Largura em Árvore de Grafos Direcionados. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2018
.
p. 105-108.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2018.3163.
