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
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?
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

 

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.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.hkuros25141en_HK
dc.identifier.spage223en_HK
dc.identifier.epage232en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats