On Colored Edge Cuts in Graphs
Resumo
In this work we present some results on the classical and parameterized complexity of finding cuts in edge-colored graphs. In general, we are interested in problems of finding cuts {A,B} which minimize or maximize the number of colors occurring in the edges with exactly one endpoint in A.
Referências
Blin, G., Bonizzoni, P., Dondi, R., Rizzi, R., and Sikora, F. (2014). Complexity insights of the minimum duplication problem. Theoretical Computer Science, 530:66 – 79.
Coudert, D., Datta, P., Perennes, S., Rivano, H., and Voge, M. (2007). Shared risk resource group complexity and approximability issues. Parallel Process. Lett., 17(2):169–184.
Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized Algorithms. Springer.
Diestel, R. (2010). Graph Theory, volume 173. Springer-Verlag, 4th edition.
Dinur, I. and Steurer, D. (2014). Analytical approach to parallel repetition. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC ’14, pages 624–633, New York, NY, USA. ACM.
Downey, R. G. and Fellows, M. R. (2013). Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer.
Felzenszwalb, P. F. and Huttenlocher, D. P. (2004). Efficient graph-based image segmentation. International Journal of Computer Vision, 59(2):167–181.
Flum, J. and Grohe, M. (2006). Parameterized Complexity Theory. Texts in Theoretical Computer Science. Springer.
Niedermeier, R. (2006). Invitation to Fixed-Parameter Algorithms, volume 31. Oxford University Press.
Porschen, S. and Speckenmeyer, E. (2007). Algorithms for variable-weighted 2-sat and dual problems. In Theory and Applications of Satisfiability Testing–SAT 2007, pages 173–186. Springer.
Shi, J. and Malik, J. (1997). Normalized cuts and image segmentation. In Computer Vision and Pattern Recognition, 1997. Proceedings., 1997 IEEE Computer Society Conference on, pages 731–737. IEEE.
Coudert, D., Datta, P., Perennes, S., Rivano, H., and Voge, M. (2007). Shared risk resource group complexity and approximability issues. Parallel Process. Lett., 17(2):169–184.
Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized Algorithms. Springer.
Diestel, R. (2010). Graph Theory, volume 173. Springer-Verlag, 4th edition.
Dinur, I. and Steurer, D. (2014). Analytical approach to parallel repetition. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC ’14, pages 624–633, New York, NY, USA. ACM.
Downey, R. G. and Fellows, M. R. (2013). Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer.
Felzenszwalb, P. F. and Huttenlocher, D. P. (2004). Efficient graph-based image segmentation. International Journal of Computer Vision, 59(2):167–181.
Flum, J. and Grohe, M. (2006). Parameterized Complexity Theory. Texts in Theoretical Computer Science. Springer.
Niedermeier, R. (2006). Invitation to Fixed-Parameter Algorithms, volume 31. Oxford University Press.
Porschen, S. and Speckenmeyer, E. (2007). Algorithms for variable-weighted 2-sat and dual problems. In Theory and Applications of Satisfiability Testing–SAT 2007, pages 173–186. Springer.
Shi, J. and Malik, J. (1997). Normalized cuts and image segmentation. In Computer Vision and Pattern Recognition, 1997. Proceedings., 1997 IEEE Computer Society Conference on, pages 731–737. IEEE.
Publicado
04/07/2016
Como Citar
FARIA, Luerbio; KLEIN, Sulamita; SAU, Ignasi; SOUZA, Uéverton S.; SUCUPIRA, Rubens.
On Colored Edge Cuts in Graphs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 1. , 2016, Porto Alegre.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2016
.
p. 780-783.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2016.9764.
