Note on the Homogeneous Set Sandwich Problem.
In: Information Processing Letters, Jg. 93 (2005-01-31), Heft 2, S. 75-81
academicJournal
Zugriff:
A homogeneous set is a non-trivial module of a graph, i.e., a non-unitary, proper subset H of a graph's vertices such that all vertices in H have the same neighbors outside H. Given two graphs G1 (V, E1), G2(V, E2), the Homogeneous Set Sandwich Problem asks whether there exists a sandwich graph GS(V, ES), E1 ⊂ Es ⊂ E2, which has a homogeneous set. Recently, Tang et al. [Inform. Process. Lett. 77 (2001) 17-22] proposed an interesting O(Δ1 . n2) algorithm for this problem, which has been considered its most efficient algorithm since. We show the incorrectness of their algorithm by presenting three counter examples. [ABSTRACT FROM AUTHOR]
| Titel: |
Note on the Homogeneous Set Sandwich Problem.
|
|---|---|
| Autor/in / Beteiligte Person: | De Figueiredo, Celina M. H. ; De Sá, Vinícius G. P. |
| Zeitschrift: | Information Processing Letters, Jg. 93 (2005-01-31), Heft 2, S. 75-81 |
| Veröffentlichung: | 2005 |
| Medientyp: | academicJournal |
| ISSN: | 0020-0190 (print) |
| DOI: | 10.1016/j.ipl.2004.09.022 |
| Schlagwort: |
|
| Sonstiges: |
|