File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Approximating biconnectivity in parallel

TitleApproximating biconnectivity in parallel
Authors
Chong, KWLam, TW
KeywordsApproximation Algorithms
Biconnectivity
Graph Algorithms
Maximum Matching
Nc
Perfect Matching
Pram
Issue Date1998
PublisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm
Citation
Algorithmica (New York), 1998, v. 21 n. 4, p. 395-410 How to Cite?
DOI: http://dx.doi.org/10.1007/PL00009221
AbstractConsider the following NP-hard problems: Given a graph G, find minimum 2-edge connected and 2-vertex connected subgraphs spanning all vertices of G. Over the past few years, exciting sequential algorithms for approximating such minimum subgraphs have been produced [6], [10]. The approximation factors are improved from 2 to 3/2 for both of the problems. 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 + ε for these two problems without computing depth-first-search trees. © 1998 Springer-Verkg New York Inc.
Persistent Identifierhttp://hdl.handle.net/10722/152307
ISSN
0178-4617
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.905
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorChong, KWen_US
dc.contributor.authorLam, TWen_US
dc.date.accessioned2012-06-26T06:37:05Z-
dc.date.available2012-06-26T06:37:05Z-
dc.date.issued1998en_US
dc.identifier.citationAlgorithmica (New York), 1998, v. 21 n. 4, p. 395-410en_US
dc.identifier.issn0178-4617en_US
dc.identifier.urihttp://hdl.handle.net/10722/152307-
dc.description.abstractConsider the following NP-hard problems: Given a graph G, find minimum 2-edge connected and 2-vertex connected subgraphs spanning all vertices of G. Over the past few years, exciting sequential algorithms for approximating such minimum subgraphs have been produced [6], [10]. The approximation factors are improved from 2 to 3/2 for both of the problems. 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 + ε for these two problems without computing depth-first-search trees. © 1998 Springer-Verkg New York Inc.en_US
dc.languageengen_US
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htmen_US
dc.relation.ispartofAlgorithmica (New York)en_US
dc.subjectApproximation Algorithmsen_US
dc.subjectBiconnectivityen_US
dc.subjectGraph Algorithmsen_US
dc.subjectMaximum Matchingen_US
dc.subjectNcen_US
dc.subjectPerfect Matchingen_US
dc.subjectPramen_US
dc.titleApproximating biconnectivity in parallelen_US
dc.typeArticleen_US
dc.identifier.emailLam, TW:twlam@cs.hku.hken_US
dc.identifier.authorityLam, TW=rp00135en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/PL00009221-
dc.identifier.scopuseid_2-s2.0-0343474141en_US
dc.identifier.hkuros40763-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0343474141&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume21en_US
dc.identifier.issue4en_US
dc.identifier.spage395en_US
dc.identifier.epage410en_US
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridChong, KW=7102553941en_US
dc.identifier.scopusauthoridLam, TW=7202523165en_US
dc.identifier.issnl0178-4617-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats