File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: An efficient algorithm for finding maximum cycle packings in reducible flow graphs

TitleAn efficient algorithm for finding maximum cycle packings in reducible flow graphs
Authors
Chen, XZang, W
KeywordsAlgorithm
Complexity
Cycle Packing
Feedback Set
Network Flow
Issue Date2006
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), 2006, v. 44 n. 3, p. 195-211 How to Cite?
DOI: http://dx.doi.org/10.1007/s00453-005-1174-x
AbstractReducible flow graphs occur naturally in connection with flowcharts of computer programs and are used extensively for code optimization and global data flow analysis. In this paper we present an O(n2 log(n 2/m)) algorithm for finding a maximum cycle packing in any weighted reducible flow graph with n vertices and m arcs; our algorithm heavily relies on Ramachandran's earlier work concerning reducible flow graphs. © 2005 Springer Science + Business Media, Inc.
Persistent Identifierhttp://hdl.handle.net/10722/156153
ISSN
0178-4617
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.905
ISI Accession Number ID
WOS:000235219800002
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorChen, Xen_US
dc.contributor.authorZang, Wen_US
dc.date.accessioned2012-08-08T08:40:37Z-
dc.date.available2012-08-08T08:40:37Z-
dc.date.issued2006en_US
dc.identifier.citationAlgorithmica (New York), 2006, v. 44 n. 3, p. 195-211en_US
dc.identifier.issn0178-4617en_US
dc.identifier.urihttp://hdl.handle.net/10722/156153-
dc.description.abstractReducible flow graphs occur naturally in connection with flowcharts of computer programs and are used extensively for code optimization and global data flow analysis. In this paper we present an O(n2 log(n 2/m)) algorithm for finding a maximum cycle packing in any weighted reducible flow graph with n vertices and m arcs; our algorithm heavily relies on Ramachandran's earlier work concerning reducible flow graphs. © 2005 Springer Science + Business Media, 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.subjectAlgorithmen_US
dc.subjectComplexityen_US
dc.subjectCycle Packingen_US
dc.subjectFeedback Seten_US
dc.subjectNetwork Flowen_US
dc.titleAn efficient algorithm for finding maximum cycle packings in reducible flow graphsen_US
dc.typeArticleen_US
dc.identifier.emailZang, W:wzang@maths.hku.hken_US
dc.identifier.authorityZang, W=rp00839en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/s00453-005-1174-xen_US
dc.identifier.scopuseid_2-s2.0-32244443037en_US
dc.identifier.hkuros116081-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-32244443037&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume44en_US
dc.identifier.issue3en_US
dc.identifier.spage195en_US
dc.identifier.epage211en_US
dc.identifier.isiWOS:000235219800002-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridChen, X=8987182300en_US
dc.identifier.scopusauthoridZang, W=7005740804en_US
dc.identifier.issnl0178-4617-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats