File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Approximating biconnectivity in parallel

TitleApproximating biconnectivity in parallel
Authors
Chong, Ka WongLam, Tak Wah
Issue Date1995
PublisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm
Citation
Annual Acm Symposium On Parallel Algorithms And Architectures, 1995, p. 224-233 How to Cite?
AbstractConsider the following NP-hard problems: Given a graph G, find the minimum 2-edge connected and 2-vertex connected subgraphs spanning all vertices of G. The past few years have produced exciting sequential algorithms for approximating such minimum subgraphs [6, 7]. The approximation factors are improved from 2 down to 5/4 and 3/2 respectively. Yet the techniques involved are all based on augmenting depth-first-search trees and no similar progress has been carried to the parallel context. This paper presents NC algorithms to achieve approximation factors of 3/2 + ε and 7/4 + ε respectively without computing depth-first-search trees.
Persistent Identifierhttp://hdl.handle.net/10722/88921
ISSN
0178-4617
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.905

 

DC FieldValueLanguage
dc.contributor.authorChong, Ka Wongen_HK
dc.contributor.authorLam, Tak Wahen_HK
dc.date.accessioned2010-09-06T09:50:09Z-
dc.date.available2010-09-06T09:50:09Z-
dc.date.issued1995en_HK
dc.identifier.citationAnnual Acm Symposium On Parallel Algorithms And Architectures, 1995, p. 224-233en_HK
dc.identifier.issn0178-4617en_HK
dc.identifier.urihttp://hdl.handle.net/10722/88921-
dc.description.abstractConsider the following NP-hard problems: Given a graph G, find the minimum 2-edge connected and 2-vertex connected subgraphs spanning all vertices of G. The past few years have produced exciting sequential algorithms for approximating such minimum subgraphs [6, 7]. The approximation factors are improved from 2 down to 5/4 and 3/2 respectively. Yet the techniques involved are all based on augmenting depth-first-search trees and no similar progress has been carried to the parallel context. This paper presents NC algorithms to achieve approximation factors of 3/2 + ε and 7/4 + ε respectively without computing depth-first-search trees.en_HK
dc.languageengen_HK
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htmen_HK
dc.relation.ispartofAnnual ACM Symposium on Parallel Algorithms and Architecturesen_HK
dc.titleApproximating biconnectivity in parallelen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0178-4617&volume=21&spage=395&epage=410&date=1998&atitle=Approximating+biconnectivity+in+parallelen_HK
dc.identifier.emailLam, Tak Wah:twlam@cs.hku.hken_HK
dc.identifier.authorityLam, Tak Wah=rp00135en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-0029179686en_HK
dc.identifier.spage224en_HK
dc.identifier.epage233en_HK
dc.identifier.scopusauthoridChong, Ka Wong=7102553941en_HK
dc.identifier.scopusauthoridLam, Tak Wah=7202523165en_HK
dc.identifier.issnl0178-4617-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats