HEURISTIC ALGORITHM FOR CONFLICT RESOLUTION PROBLEM IN MULTISTAGE INTERCONNECTION NETWORKS.

Jitender S. Deogun, Zhixi Fang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

A graph model called a conflict graph is presented to describe the conflict-resolution problem in multistage interconnection networks. The properties of the conflict graph are investigated, and it is shown that the conflict-resolution problem is equivalent to the node-coloring problem in the conflict graph. A heuristic algorithm with performance P(G) equals O(log//2 N) is developed, offering a considerable improvement over the bounds of the currently best algorithm known.

Original languageEnglish (US)
Title of host publicationProceedings of the International Conference on Parallel Processing
EditorsSartaj K. Sahni
PublisherPennsylvania State Univ Press
Pages475-478
Number of pages4
ISBN (Print)0271006080
StatePublished - Dec 1 1987
EventProc Int Conf Parallel Process 1987 - Universal Park, PA, USA
Duration: Aug 17 1987Aug 21 1987

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918

Other

OtherProc Int Conf Parallel Process 1987
CityUniversal Park, PA, USA
Period8/17/878/21/87

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'HEURISTIC ALGORITHM FOR CONFLICT RESOLUTION PROBLEM IN MULTISTAGE INTERCONNECTION NETWORKS.'. Together they form a unique fingerprint.

  • Cite this

    Deogun, J. S., & Fang, Z. (1987). HEURISTIC ALGORITHM FOR CONFLICT RESOLUTION PROBLEM IN MULTISTAGE INTERCONNECTION NETWORKS. In S. K. Sahni (Ed.), Proceedings of the International Conference on Parallel Processing (pp. 475-478). (Proceedings of the International Conference on Parallel Processing). Pennsylvania State Univ Press.