File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Towards More Precise Parallel Biconnectivity Approximation

TitleTowards More Precise Parallel Biconnectivity Approximation
Authors
Chong, KWLam, TW
Issue Date1996
PublisherSpringer.
Citation
The 7th International Symposium on Algorithms and Computation. In Asano, T, Igarashi, Y and Nagamochi, H et al (Eds.). Algorithms and Computation, v. 1178, p. 223-232. Berlin, Heidelberg: Springer, 1996 How to Cite?
DOI: http://dx.doi.org/10.1007/BFb0009498
AbstractThe problem of finding a minimum biconnected spanning subgraph of an undirected graph is NP-hard. This paper, improving a chain of work [1, 10, 3, 4], gives the first NC algorithm for approximating a minimum biconnected subgraph with an approximation factor approaching 3/2. This result matches the performance of the currently best sequential approximation algorithm [7].
Persistent Identifierhttp://hdl.handle.net/10722/93021
ISBN
978-3-540-62048-8
ISSN
0302-9743
2023 SCImago Journal Rankings: 0.606

 

DC FieldValueLanguage
dc.contributor.authorChong, KWen_HK
dc.contributor.authorLam, TWen_HK
dc.date.accessioned2010-09-25T14:48:28Z-
dc.date.available2010-09-25T14:48:28Z-
dc.date.issued1996en_HK
dc.identifier.citationThe 7th International Symposium on Algorithms and Computation. In Asano, T, Igarashi, Y and Nagamochi, H et al (Eds.). Algorithms and Computation, v. 1178, p. 223-232. Berlin, Heidelberg: Springer, 1996en_HK
dc.identifier.isbn978-3-540-62048-8-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/93021-
dc.description.abstractThe problem of finding a minimum biconnected spanning subgraph of an undirected graph is NP-hard. This paper, improving a chain of work [1, 10, 3, 4], gives the first NC algorithm for approximating a minimum biconnected subgraph with an approximation factor approaching 3/2. This result matches the performance of the currently best sequential approximation algorithm [7].-
dc.languageengen_HK
dc.publisherSpringer.en_HK
dc.relation.ispartofAlgorithms and Computationen_HK
dc.titleTowards More Precise Parallel Biconnectivity Approximationen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailLam, TW: twlam@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/BFb0009498-
dc.identifier.scopuseid_2-s2.0-84990197375-
dc.identifier.hkuros25141en_HK
dc.identifier.spage223en_HK
dc.identifier.epage232en_HK
dc.identifier.eissn1611-3349-
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats