English  |  正體中文  |  简体中文  |  Items with full text/Total items : 58286/91808 (63%)
Visitors : 13814860      Online Users : 71
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library & TKU 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
    Please use this identifier to cite or link to this item: http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/96127

    Title: Smallest Bipartite Bridge-connectivity Augmentation
    Authors: Huang, Pei-Chi;Wei, Hsin-Wen;Lu, Wan-Chen;Shih, Wei-Kuan;Hsu, Tsan-sheng
    Contributors: 淡江大學電機工程學系
    Keywords: 2-edge-connectivity;Bridge-connectivity;Data security;Bipartite graph augmentation
    Date: 2009-07
    Issue Date: 2014-03-03 16:27:08 (UTC+8)
    Publisher: New York: Springer New York LLC
    Abstract: This paper addresses two augmentation problems related to bipartite graphs. The first, a fundamental graph-theoretical problem, is how to add a set of edges with the smallest possible cardinality so that the resulting graph is 2-edge-connected, i.e., bridge-connected, and still bipartite. The second problem, which arises naturally from research on the security of statistical data, is how to add edges so that the resulting graph is simple and does not contain any bridges. In both cases, after adding edges, the graph can be either a simple graph or, if necessary, a multi-graph. Our approach then determines whether or not such an augmentation is possible.
    We propose a number of simple linear-time algorithms to solve both problems. Given the well-known bridge-block data structure for an input graph, the algorithms run in O(log n) parallel time on an EREW PRAM using a linear number of processors, where n is the number of vertices in the input graph. We note that there is already a polynomial time algorithm that solves the first augmentation problem related to graphs with a given general partition constraint in O(n(m+nlog n)log n) time, where m is the number of distinct edges in the input graph. We are unaware of any results for the second problem.
    Relation: Algorithmica 54(3), pp.353-378
    DOI: 10.1007/s00453-007-9127-1
    Appears in Collections:[Graduate Institute & Department of Electrical Engineering] Journal Article

    Files in This Item:

    File Description SizeFormat

    All items in 機構典藏 are protected by copyright, with all rights reserved.

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