File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Minimum-weight vertex cover problem for two-class resource connection graphs

TitleMinimum-weight vertex cover problem for two-class resource connection graphs
Authors
Chen, JSJLi, VOK
Issue Date1993
PublisherElsevier Inc. The Journal's web site is located at http://www.elsevier.com/locate/ins
Citation
Information Sciences, 1993, v. 74 n. 1-2, p. 53-71 How to Cite?
AbstractWe study the minimum-weight vertex cover problem for a special type of three-partite graphs called two-class resource connection graphs. This problem is important due to its various application in different problem domains, especially in broadcast distributed computing systems. A mapping between this problem and some practical problems is developed and it is shown that these problems are equivalent. We prove the minimum-weight vertex cover problem for two-class resource connection graphs is NP-hard. Some properties of such graphs are identified and an efficient heuristic based on the identified properties is given. Two interesting special cases of this problem are also discussed. © 1993.
Persistent Identifierhttp://hdl.handle.net/10722/154987
ISSN
0020-0255
2022 Impact Factor: 8.1
2023 SCImago Journal Rankings: 2.238
ISI Accession Number ID
WOS:A1993LZ83500003

 

DC FieldValueLanguage
dc.contributor.authorChen, JSJen_US
dc.contributor.authorLi, VOKen_US
dc.date.accessioned2012-08-08T08:31:24Z-
dc.date.available2012-08-08T08:31:24Z-
dc.date.issued1993en_US
dc.identifier.citationInformation Sciences, 1993, v. 74 n. 1-2, p. 53-71en_US
dc.identifier.issn0020-0255en_US
dc.identifier.urihttp://hdl.handle.net/10722/154987-
dc.description.abstractWe study the minimum-weight vertex cover problem for a special type of three-partite graphs called two-class resource connection graphs. This problem is important due to its various application in different problem domains, especially in broadcast distributed computing systems. A mapping between this problem and some practical problems is developed and it is shown that these problems are equivalent. We prove the minimum-weight vertex cover problem for two-class resource connection graphs is NP-hard. Some properties of such graphs are identified and an efficient heuristic based on the identified properties is given. Two interesting special cases of this problem are also discussed. © 1993.en_US
dc.languageengen_US
dc.publisherElsevier Inc. The Journal's web site is located at http://www.elsevier.com/locate/insen_US
dc.relation.ispartofInformation Sciencesen_US
dc.titleMinimum-weight vertex cover problem for two-class resource connection graphsen_US
dc.typeArticleen_US
dc.identifier.emailLi, VOK:vli@eee.hku.hken_US
dc.identifier.authorityLi, VOK=rp00150en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.scopuseid_2-s2.0-0027683563en_US
dc.identifier.volume74en_US
dc.identifier.issue1-2en_US
dc.identifier.spage53en_US
dc.identifier.epage71en_US
dc.identifier.isiWOS:A1993LZ83500003-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridChen, JSJ=37046615000en_US
dc.identifier.scopusauthoridLi, VOK=7202621685en_US
dc.identifier.issnl0020-0255-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats