NDLI: Linear-Processor NC Algorithms for Planar Directed Graphs I: Strongly Connected Components

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Kao, Ming-Yang
Copyright Year	1993
Abstract	Finding strongly connected components is a fundamental step in many algorithms for directed graphs. In sequential computation this problem has an optimal linear-time algorithm. In parallel computation, however, it remains an open problem whether polylogarithmic time and a linear number of processors are sufficient for computing the strongly connected components on a parallel random-access machine. This paper provides the first nontrivial partial solution to the open problem: for a planar directed graph of size n the strongly connected components can be computed deterministically in $O(\log ^3 n)$ time with ${n / {\log n}}$ processors. The algorithm runs on a parallel random-access machine that allows concurrent reads and concurrent writes in its shared memory and, in case of a write conflict, permits an arbitrary processor to succeed.
Starting Page	431
Ending Page	459
Page Count	29
File Format	PDF
ISSN	00975397
DOI	10.1137/0222032
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	3
Volume Number	22
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-07-31
Access Restriction	Subscribed
Subject Keyword	strongly connected components planar directed graphs planar topology planar orientation vertex contraction edge cutting vertex expansion linear-processor NC algorithms
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

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