Image component labelling on the star graph using divide and conquer

Image component labelling on the star graph using divide and conquer

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IEE Proceedings - Computers and Digital Techniques — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Since its introduction in the literature, the star interconnection network has become a popular architecture for connecting parallel processors. It compares favourably with the famous hypercube as far as basic network attributes are concerned. Its degree and diameter are sublogarithmic with respect to the total number of processors and it enjoys fault tolerance and symmetry properties. It remains to be seen whether known efficient algorithms that have been developed for other interconnection network architectures can be implemented efficiently on the star, and how well these will perform in the presence of faults in the network. The authors address this question for image analysis algorithms, specifically for the image component labelling problem. Component labelling is a fundamental and basic task common to virtually all image analysis problems. The star interconnection network is modelled with a graph, an innovative grid embedding into the star is used and an efficient algorithm to solve the image component labelling problem on the star graph is developed. The authors then analyse the performance of the algorithm in the fault-free star graph.


    1. 1)
      • Akers, S.B., Harel, D., Krishnamurthy, B.: `The star graph: an attractivealternative to the n-cube', Proceedings of international conference on Parallel processing, 1987, p. 393–400.
    2. 2)
      • Akers, S.B., Krishnamurthy, B.: `The fault tolerance of star graphs', Proceedings of secondinternational conference on Supercomputing, 1987, p. 270–276.
    3. 3)
      • N. Bagherzadeh , N. Nassif , S. Latifi . A routing and broadcasting scheme onfaulty star graphs. IEEE Trans. Comput. , 11 , 1398 - 1403
    4. 4)
      • R.E. Cypher , J.L.C. Sanz , L. Snyder . Hypercube and shuffle-exchange algorithmsfor image component labeling. J. Algorithms , 1 , 140 - 150
    5. 5)
      • R.E. Cypher , J.L.C. Sanz , L. Snyder . Algorithms for image component labeling onSIMD mesh-connected computers. IEEE Trans. Comput. , 2 , 276 - 281
    6. 6)
      • Nassif, N.: `A study of star graph algorithms', 1996, PhD, University of California Irvine, Department of Electrical and Computer Engineering, Irvine, CA, 92697.
    7. 7)
      • Nigam, M., Sahni, S., Krishnamurthy, B.: `Embedding Hamiltonians and hypercubes in star interconnection networks', Proceedings of international conference on Parallel processing, 1990, p. 340–343.
    8. 8)
      • A.V. Aho , J.E. Hopcroft , J.D. Ullman . (1974) The design and analysis of computer algorithms.
    9. 9)
      • V.E. Mendia , D. Sarkar . Optimal broadcasting on the star graph. IEEE Trans. Parallel Distrib. Syst. , 4 , 389 - 396

Related content

This is a required field
Please enter a valid email address