English  |  正體中文  |  简体中文  |  Items with full text/Total items : 54367/62174 (87%)
Visitors : 14781429      Online Users : 95
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTHU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version
    National Tsing Hua University Institutional Repository > 歷任校長 > 李家同 (1993-1994) > 期刊論文  >  A Linear Time Algorithm to Solve the Weighted Perfect Domination Problem in Series-Parallel Graphs

    Please use this identifier to cite or link to this item: http://nthur.lib.nthu.edu.tw/dspace/handle/987654321/80813

    Title: A Linear Time Algorithm to Solve the Weighted Perfect Domination Problem in Series-Parallel Graphs
    Authors: Yen, C. C.;Lee, R. C. T.
    教師: 李家同
    Date: 1994
    Publisher: Elsevier
    Relation: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, Elsevier, Volume 73, Issue 1, FEB 24 1994, Pages 192-198
    Keywords: Series-parallel graph
    Parsing tree
    Perfect domination
    Dynamic programming
    Abstract: In this paper, we consider the weighted perfect domination problem in series-parallel graphs. Suppose G = (V, E) is a graph in which every vertex x is-an-element-of V has a cost c(x) and every edge e is-an-element-of E has a cost c(e). The weighted perfect domination problem is to find a subset D subset-of V such that every vertex not in D is adjacent to exactly one vertex in D and its total cost c(D) = SIGMA{c(x): x is-an-element-of D} + SIGMA{c(x, y): x is-not-an-element-of D, y is-an-element-of D and (x, y) is-an-element-of E} is minimum. This problem is NP-complete for bipartite graphs and chordal graphs. In this paper, we present a linear time algorithm for the problem in series-parallel graphs.
    Relation Link: http://www.elsevier.com/wps/find/homepage.cws_home
    URI: http://nthur.lib.nthu.edu.tw/dspace/handle/987654321/80813
    Appears in Collections:[李家同 (1993-1994)] 期刊論文
    [資訊工程學系] 期刊論文

    Files in This Item:

    File SizeFormat


    SFX Query


    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback