English  |  正體中文  |  简体中文  |  Items with full text/Total items : 54367/62174 (87%)
Visitors : 14639627      Online Users : 53
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 > 電機資訊學院 > 資訊工程學系 > 期刊論文 >  Perfect edge domination and efficient edge domination in graphs


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


    Title: Perfect edge domination and efficient edge domination in graphs
    Authors: Lu, Chin Lung;Ko, Ming-Tat;Tang, Chuan Yi
    教師: 唐傳義
    Date: 2002
    Publisher: Elsevier
    Relation: DISCRETE APPLIED MATHEMATICS,Volume 119,Issue 3,Pages 227-250,JUL 15 2002
    Keywords: Algorithms
    Perfect edge domination
    E cient edge domination
    Planar bipartite graphs
    Generalized series
    parallel graphs
    Chordal graphs
    Abstract: Let G=(V,E) be a finite and undirected graph without loops and multiple edges. An edge is said to dominate itself and any edge adjacent to it. A subset D of E is called a perfect edge dominating set if every edge of E \ D is dominated by exactly one edge in D and an efficient edge dominating set if every edge of E is dominated by exactly one edge in D. The perfect (efficient) edge domination problem is to find a perfect (efficient) edge dominating set of minimum size in G. Suppose that each edge e is associated with a real number w(e) as its weight. Then, the weighted perfect (efficient) edge domination problem is to calculate a perfect (efficient) edge dominating set D such that the weight w(D) of D is minimum, where w(D)= summation e is a member of the set of D w(e). In this paper, we show that the perfect (efficient) edge domination problem is NP-complete on bipartite (planar bipartite) graphs. Moreover, we present linear-time algorithms to solve the weighted perfect (efficient) edge domination problem on generalized series-parallel graphs and chordal graphs.
    URI: http://www.elsevier.com/
    http://nthur.lib.nthu.edu.tw/dspace/handle/987654321/66289
    Appears in Collections:[資訊工程學系] 期刊論文

    Files in This Item:

    File Description SizeFormat
    index.html0KbHTML274View/Open


    在NTHUR中所有的資料項目都受到原著作權保護,僅提供學術研究及教育使用,敬請尊重著作權人之權益。若須利用於商業或營利,請先取得著作權人授權。
    若發現本網站收錄之內容有侵害著作權人權益之情事,請權利人通知本網站管理者(smluo@lib.nthu.edu.tw),管理者將立即採取移除該內容等補救措施。

    SFX Query

    與系統管理員聯絡

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