The Homogeneous Set Sandwich Problem

• Vinícius Gusmão Pereira de Sá UFRJ

Resumo

Homogeneous sets have proved useful for the construction of graph decomposition procedures. Sandwich graphs are obtained from two pre-defined graphs which provide them with both mandatory and optional edges. Given such a pair of graphs, the Homogeneous Set Sandwich Problem (HSSP) searches for a sandwich graph which contains a homogeneous set. This thesis presents the development of techniques for solving the HSSP and culminates in the correction of the established upper bounds for its time complexity. Such results comprise the description of thoroughly depicted counterexamples which prove the incorrectness of the (so far) best published HSSP algorithm, along with the proposal of a new, faster algorithm.

Referências

Cerioli, M. R., Everett, H., de Figueiredo, C. M. H., and Klein, S. (1998). The homogeneous set sandwich problem. Information Processing Letters, 67:31–35.

Dantas, S., Faria, L., and de Figueiredo, C. M. H. (2002). On the complexity of (k,l)-graph sandwich problems. Lecture Notes in Computer Science, Proceedings of WG 2002(2573):92–101.

de Figueiredo, C. M. H., Klein, S., and Vušković, K. (2002). The graph sandwich problem for 1-join composition is NP-complete. Discrete Appl. Math., 121:73–82.

Golumbic, M. C. (1998). Matrix sandwich problems. Linear Algebra Appl., 277:239–251.

Golumbic, M. C., Kaplan, H., and Shamir, R. (1995). Graph sandwich problems. Journal of Algorithms, 19:449–473.

Golumbic, M. C. and Wassermann, A. (1998). Complexity and algorithms for graph and hypergraph sandwich problems. Graphs Combin., 14:223–239.

Kaplan, H. and Shamir, R. (1999). Bounded degree interval sandwich problems. Algorithmica, 24:96–104.

Lovász, L. (1972). Normal hypergraphs and the perfect graph conjecture. Discrete Math., 2:253–267.

Tang, S., Yeh, F., and Wang, Y. (2001). An efficient algorithm for solving the homogeneous set sandwich problem. Information Processing Letters, 77:17–22.