HEURISTIC ALGORITHM FOR CONFLICT RESOLUTION PROBLEM IN MULTISTAGE INTERCONNECTION NETWORKS.

Jitender S. Deogun; Zhixi Fang

HEURISTIC ALGORITHM FOR CONFLICT RESOLUTION PROBLEM IN MULTISTAGE INTERCONNECTION NETWORKS.

Jitender S. Deogun, Zhixi Fang

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Proceedings of the International Conference on Parallel Processing
Editors	Sartaj K. Sahni
Publisher	Pennsylvania State Univ Press
Pages	475-478
Number of pages	4
ISBN (Print)	0271006080
State	Published - 1987
Event	Proc Int Conf Parallel Process 1987 - Universal Park, PA, USA Duration: Aug 17 1987 → Aug 21 1987

Publication series

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

Other

Other	Proc Int Conf Parallel Process 1987
City	Universal Park, PA, USA
Period	8/17/87 → 8/21/87

ASJC Scopus subject areas

Hardware and Architecture

Cite this

HEURISTIC ALGORITHM FOR CONFLICT RESOLUTION PROBLEM IN MULTISTAGE INTERCONNECTION NETWORKS. / Deogun, Jitender S.; Fang, Zhixi.

Proceedings of the International Conference on Parallel Processing. ed. / Sartaj K. Sahni. Pennsylvania State Univ Press, 1987. p. 475-478 (Proceedings of the International Conference on Parallel Processing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Deogun, JS & Fang, Z 1987, HEURISTIC ALGORITHM FOR CONFLICT RESOLUTION PROBLEM IN MULTISTAGE INTERCONNECTION NETWORKS. in SK Sahni (ed.), Proceedings of the International Conference on Parallel Processing. Proceedings of the International Conference on Parallel Processing, Pennsylvania State Univ Press, pp. 475-478, Proc Int Conf Parallel Process 1987, Universal Park, PA, USA, 8/17/87.

@inproceedings{2816b4173f07421db293354ebbd2b0e0,

title = "HEURISTIC ALGORITHM FOR CONFLICT RESOLUTION PROBLEM IN MULTISTAGE INTERCONNECTION NETWORKS.",

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.",

author = "Deogun, {Jitender S.} and Zhixi Fang",

year = "1987",

language = "English (US)",

isbn = "0271006080",

series = "Proceedings of the International Conference on Parallel Processing",

publisher = "Pennsylvania State Univ Press",

pages = "475--478",

editor = "Sahni, {Sartaj K.}",

booktitle = "Proceedings of the International Conference on Parallel Processing",

note = "Proc Int Conf Parallel Process 1987 ; Conference date: 17-08-1987 Through 21-08-1987",

}

TY - GEN

T1 - HEURISTIC ALGORITHM FOR CONFLICT RESOLUTION PROBLEM IN MULTISTAGE INTERCONNECTION NETWORKS.

AU - Deogun, Jitender S.

AU - Fang, Zhixi

PY - 1987

Y1 - 1987

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0023536119&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0023536119&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0023536119

SN - 0271006080

T3 - Proceedings of the International Conference on Parallel Processing

SP - 475

EP - 478

BT - Proceedings of the International Conference on Parallel Processing

A2 - Sahni, Sartaj K.

PB - Pennsylvania State Univ Press

T2 - Proc Int Conf Parallel Process 1987

Y2 - 17 August 1987 through 21 August 1987

ER -

HEURISTIC ALGORITHM FOR CONFLICT RESOLUTION PROBLEM IN MULTISTAGE INTERCONNECTION NETWORKS.

Abstract

Publication series

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this