On Colored Edge Cuts in Graphs
Abstract
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.
References
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.
Published
2016-07-04
How to Cite
FARIA, Luerbio; KLEIN, Sulamita; SAU, Ignasi; SOUZA, Uéverton S.; SUCUPIRA, Rubens.
On Colored Edge Cuts in Graphs. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (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.
