A Fast Algorithm for Augmenting Edge-Connectivity by One with Bipartition Constraints

スポンサーリンク

概要

• 論文の詳細を見る

• The k-edge-connectivity augmentation problem with bipartition constraints (kECABP, for short) is defined by “Given an undirected graph G=(V,E) and a bipartition π={VB,VW} of V with VB∩VW=∅, find an edge set Ef of minimum cardinality, consisting of edges that connect VB and VW, such that G'=(V,E∪Ef) is k-edge-connected.” The problem has applications for security of statistical data stored in a cross tabulated table, and so on. In this paper we propose a fast algorithm for finding an optimal solution to (σ+1)ECABP in O(|V||E|+|V2|log |V|) time when G is σ-edge-connected (σ > 0), and show that the problem can be solved in linear time if σ ∈ {1,2}.

• 2012-03-01

著者

• Taoka Satoshi

  Graduate School Of Engineering Hiroshima University

• Oki Tadachika

  Graduate School Of Engineering Hiroshima University

• Taoka Satoshi

  Hiroshima Univ. Higashihiroshima‐shi Jpn

• Watanabe Toshimasa

  Hiroshima Univ. Higashi‐hiroshima Jpn

• Mashima Toshiya

  Department Of Computer Engineering Faculty Of Information Sciences Hiroshima City University

• Watanabe Toshimasa

  Graduate School Of Engineering Hiroshima Univ.

• Mashima Toshiya

  Department Of Information And Communications Technology Faculty Of Engineering Hiroshima International University

関連論文

• Time Complexity Analysis of the Legal Firing Sequence Problem of Petri Nets with Inhibitor Arcs(Concurrent Systems,Concurrent/Hybrid Systems: Theory and Applications)
• A Fast Algorithm for (σ+1)-Edge-Connectivity Augmentation of a σ-Edge-Connected Graph with Multipartition Constraints
• A 2-Approximation Algorithm 2-ABIS for 2-Vertex-Connectivity Augmentation of Specified Vertices in a Graph
• A (2 - 2/|L|)-Approximation Algorithm R2VS or R2ES to 2-Vertex- or 2-Edge-Connect Specified Vertices in a Graph
• Efficiently Computing Minimal-Support Nonnegative Integer Invariants of Petri Nets
• Two Enhanced Heuristic Algorithms for the Minimum Initial Marking Problem of Petri Nets
• Improved Heuristic Algorithms for Minimizing Initial Markings of Petri Nets(Concurrent/Hybrid Systems : Theory and Applications)
• Experimental Evaluation of Two Algorithms for Computing Petri Net Invariants(Special Section on Concurrent Systems Technology)
• Enhancing PC Cluster-Based Parallel Branch-and-Bound Algorithms for the Graph Coloring Problem
• Enhanced Approximation Algorithms for Maximum Weight Matchings of Graphs
• Performance Comparison of Algorithms for the Dynamic Shortest Path Problem(Selected Papers from the 19th Workshop on Circuits and Systems in Karuizawa)
• Performance comparison of algorithms for the dynamic shortest path problem (グラフアルゴリスム)
• Finding Minimal Siphons in General Petri Nets (Special Section on Description Models for Concurrent Systems and Their Applications)
• Graph Augmentation Problems with Degree-Unchangeable Vertices(Special Section of Selected Papers from the 13th Workshop on Circuits and Systems in Karuizawa)
• A linear time algorithm for tri-connectivity augmentation of bi-connected graphs with upper bounds on vertex-degree increase (第21回 回路とシステム軽井沢ワークショップ論文集) -- (グラフアルゴリズム)
• On Minimum k-Edge-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree(Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)
• Bi-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree Increase(Graph Algorithm, Foundations of Computer Science)
• A 2-Approximation Algorithm to (k+1)-Edge-Connect a Specified Set of Vertices in a k-Edge-Connected Graph(Discrete Mathematics and Its Applications)
• A Linear Time Algorithm for Bi-Connectivity Augmentation of Graphs with Upper Bounds on Vertex-Degree Increase(Selected Papers from the 17th Workshop on Circuits and Systems in Karuizawa)
• Extracting Minimal Siphon-Traps of Petri Nets and Its Application to Computing Nonnegative Integer-Invariants(Special Section on Concurrent System Technology and Its Application to Multiple Agent Systems)
• Experimental Evaluation of Maximum-Supply Partitioning Algorithms for Demand-Supply Graphs(Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)
• Siphon-Trap-Based Algorithms for Efficiently Computing Petri Net Invariants(Selected Papers from the 17th Workshop on Circuits and Systems in Karuizawa)
• FOREWORD (Special Section on Discrete Mathematics and Its Applications)
• Tri-connectivity augmentation problems for bi-connected graphs with upper bounds on vertex-degree increase (ネツトワークの信頼性)
• FOREWORD
• The Marking Construction Problem of Petri Nets and Its Heuristic Algorithms
• A Fast Algorithm for Augmenting Edge-Connectivity by One with Bipartition Constraints
• Computing-Based Performance Analysis of Approximation Algorithms for the Minimum Weight Vertex Cover Problem of Graphs
• Two Heuristic Algorithms for the Minimum Initial Marking Problem of Timed Petri Nets

もっと見る 閉じる

スポンサーリンク