NDLI: Computing dominators and its applications on processor arrays with reconfigurable bus systems

Content Provider	IEEE Xplore Digital Library
Author	Tzong-Wann Kao Shi-Jinn Horng
Copyright Year	1996
Description	Author affiliation: Dept. of Electron. Eng., Kuang Wu Inst. of Technol. & Commerce, Peito, Taiwan (Tzong-Wann Kao)
Abstract	Presents an efficient improvement of processor complexity while solving some connectivity problems in processor arrays with reconfigurable bus systems. We first derive two constant time algorithms in the proposed parallel processing system for computing the dominators and the dominator tree of an undirected graph either using a 9-D n/spl times/n/spl times/n processors or a 2-D n/sup 2//spl times/n/sup 2/ processors, where n is the number of vertices of the graph. Then based on the dominator tree algorithm, we also solve many other graph connectivity problems in constant time. They are the articulation points, bridges, biconnected components, and bridge-connected components problems in undirected graphs.
Starting Page	302
Ending Page	308
File Size	785581
Page Count	7
File Format	PDF
ISBN	0818674601
ISSN	10874089
DOI	10.1109/ISPAN.1996.508997
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1996-06-12
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Tree graphs Bridges Computational modeling Parallel algorithms Phase change random access memory Business Parallel processing Concurrent computing Processor scheduling Computer networks
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Approximate and exact parallel scheduling with applications to list, tree and graph problems

Parallel computing dominators on hypercube multiprocessors

Parallel maximum matching algorithms in interval graphs

Parallel algorithms for the medial axis transform on linear arrays with a reconfigurable pipelined bus system

Finding biconnected componemts and computing tree functions in logarithmic parallel time

Efficient graph algorithms on a linear array with a reconfigurable pipelined bus system

Efficient parallel algorithms for tree-decomposition and related problems

A deterministic parallel algorithm for planar graphs isomorphism

A near-optimal parallel algorithm for edge-coloring outerplanar graphs

Computing dominators and its applications on processor arrays with reconfigurable bus systems

Similar Documents

Approximate and exact parallel scheduling with applications to list, tree and graph problems

Parallel computing dominators on hypercube multiprocessors

Parallel maximum matching algorithms in interval graphs

Parallel algorithms for the medial axis transform on linear arrays with a reconfigurable pipelined bus system

Finding biconnected componemts and computing tree functions in logarithmic parallel time

Efficient graph algorithms on a linear array with a reconfigurable pipelined bus system

Efficient parallel algorithms for tree-decomposition and related problems

A deterministic parallel algorithm for planar graphs isomorphism

A near-optimal parallel algorithm for edge-coloring outerplanar graphs

Computing dominators and its applications on processor arrays with reconfigurable bus systems