The Problem of where to Locate p-Sinks in a Flow Network: Complexity Approach
スポンサーリンク
概要
- 論文の詳細を見る
The p-collection problem is where to locate p sinks in a flow network such that the value of a maximum flow is maximum. In this paper we show complexity results of the p-collection problem. We prove that the decision problem corresponding to the p-collection problem is strongly NP-complete.Although location problems (the p-center problem and the p-median problem) in networks and flow networks with tree structure is solvable in polynomial time, we prove that the decision problem of the p-collection problem in networks with tree structure, is weakly NP-complete. And we show a polynomial time algorithm for the subproblem of the p-collection problem such that the degree sum of vertices with degree≧3 in a network, is bound to some constant K≧0.
- 社団法人電子情報通信学会の論文
- 1996-09-25
著者
-
SENGOKU Masakazu
Dept. of Information Engineering, Niigata University
-
WATANABE Kaoru
The author is with Osaka Electro-Communication University
-
WATANABE Kaoru
Graduate School of Science and Technology, Niigata University
-
TAMURA Hiroshi
Niigata Institute of Technology
-
SENGOKU Masakazu
Graduate School of Science and Technology, Niigata University
-
Sengoku Masakazu
Dept. Of Information Engineering Niigata University
-
Sengoku Masakazu
Graduate School Of Science And Technology Niigata University
-
Tamura H
Niigata Institute Of Technology
-
Watanabe K
Graduate School Of Information Science Nara Institute Of Science And Technology
-
Sengoku M
Dept. Of Information Engineering Niigata University
-
Sengoku Masakazu
The Authors Are With The Department Of Information Engineering Niigata University
-
Watanabe Kaoru
Graduate School of Information Science, Nara Institute of Science and Technology
関連論文
- Polarimetric Enhancement in Radar Channel Imagery
- Fundamental Study on Synthetic Aperture FM-CW Radar Polarimetry
- Exact Minimization of Free BDDs and Its Application to Pass-Transistor Logic Optimization (Special Section on VLSI Design and CAD Algorithms)
- Hardware Synthesis from C Programs with Estimation of Bit Length of Variables (Special Section on VLSI Design and CAD Algorithms)
- Timing Verification of Sequential Logic Circuits Based on Controlled Multi-Clock Path Analysis (Special Section on VLSI Design and CAD Algorithms)
- Effects of Localized Distribution of Terminals and Mobility on Performance Improvement by Direct Communication(Multi-dimensional Mobile Information Networks)
- SB-10-2 Effects of Mobility and Capacity on Cell Extension by Wireless Multi-hop Networking
- Analysis of Communication Traffic Characteristics of a Two-Hop Wireless Network(Special Section on Multi-dimensional Mobile Information Networks)
- A Scheduling Problem in Multihop Networks
- Analysis of Connection Delay in Cellular Mobile Communication Systems Using Dynamic Channel Assignment (Special Section on Mutli-dimensional Mobile Information Network)
- The p-Collection Problem in a Flow Network with Lower Bounds (Special Section on Discrete Mathematics and Its Applications)
- Teletraffic Characteristics in Prioritized Handoff Control Method Considering Reattempt Calls (Special Issue on Personal, Indoor and Mobile Radio Communications)
- Evaluation of Teletraffic in Cellular Communication Systems Using Multi-Connections for Soft Handoff(Special Section on Multi-dimensional Mobile Information Networks)
- Mobile ATM Network Using Concentrated Base Station Architecture (Special Section on Multi-dimensional Mobile Information Networks)
- Optimal Problem for Contrast Enhancement in Polarimetric Radar Remote Sensing
- Stable Decomposition of Mueller Matrix
- A Time-Domain Filtering Scheme for the Modified Root-MUSIC Algorithm
- BS-7-37 An Experimental Analysis of Intermittent Connectivity in Delay Tolerant Networks(BS-7. Network Planning, Control and Management)
- Two Dimensional Equalization Scheme of Orthogonal Coding Multi-Carrier CDMA(Special Section of Papers Selected from ITC-CSCC'97)
- Bit Error Rate Evaluation of Delay Time Control Scheme for Reverse Channel on Orthogonal Coding Multi-Carrier CDMA (Special Section on Mutli-dimensional Mobile Information Network)
- Analysis of Mean Waiting Time for Delivery of a Message in Mobile Multi-Hop Networks
- Characterization of Minimum Route MTM in One-Dimensional Multi-Hop Wireless Networks
- Characterization of Minimum Route ETX in Multi-Hop Wireless Networks
- Theoretical Analysis of Route Expected Transmission Count in Multi-Hop Wireless Networks
- Analysis and Relative Evaluation of Connectivity of a Mobile Multi-Hop Network
- Synthesis of Both the Enantiomers of trans-Chrysanthenol and trans-Chrysanthenyl Acetate as the Characteristic Major Constituents of Kougiku
- Simple Synthesis of Dehydrololiolide
- Effect of a New Channel Assignment Strategy on Multihop Wireless Networks(Ad-hoc Network)(Mobile Multimedia Communications)
- Covering Problems in the p-Collection Problems
- On a Generalization of a Covering Problem Called Single Cover on Undirected Flow Networks (Special Section of Selected Papers from the 9th Karuizawa Workshop on Circuits and Systems)
- The Problem of where to Locate p-Sinks in a Flow Network: Complexity Approach
- Development in Graph- and/or Network-Theoretic Research of Cellular Mobile Communication Channel Assignment Problems (Special Section on Surveys of Researches in CAS Fields in the Last Two Decadeses, II(
- Realization Problems of a Tree with a Transmission Number Sequence (Special Section on the 6th Karuizawa Workshop on Circuits and Systems)
- On a Sufficient Condition for a Matrix to be the Synchronic Distance Matrix of a Marked Graph (Special Section on Nets-Oriented Software Specification and Design)
- A Perspective on Next-Generation Ad Hoc Networks : A Proposal for an Open Community Network : Special Section on the 10th Anniversary of Trans. Fundamentals : Last Decade and 21st Century
- Multi-Cycle Path Detection Based on Propositional Satisfiability with CNF Simplification Using Adaptive Variable Insertion (Special Section on VLSI Design and CAD Algorithms)
- Bit Length Optimization of Fractional Part on Floating to Fixed Point Conversion for High-Level Synthesis(Logic and High Synthesis)(VLSI Design and CAD Algorithms)
- A CMOS Rail-to-Rail Current Conveyer and Its Applications to Current-Mode Filters(Special Section on Papers Selected from ITC-CSCC 2002)
- A CMOS Rail-to-Rail Current Conveyor
- Look Up Table Compaction Based on Folding of Logic Functions(Special Section on VLSI Design and CAD Algorithms)
- Class A CMOS Current Conveyors
- A Clock-Feedthrough Compensated Switched-Current Memory Cell
- Characteristics of Dynamic Channel Assignment in Cellular Systems with Reuse Partitioning (Special Section on Multi-dimensional Mobile Information Network)
- An Approach to Dynamic Channel Assignment in a Cellular Mobile Communication System Using a Neural Network (Special Section of Papers Selected from JTC-CSCC'93)
- Flooding Schemes for Clustered Ad Hoc Networks
- Clique Packing Approximation for Analysis of Teletraffic Characteristics of Dynamic Channel Assignment Considering Mobility (Special Section on Multi-dimensional Mobile Information Networks)
- Reduction of Surface Clutter by a Polarimetric FM-CW Radar in Underground Target Detection
- Detection of Objects Buried in Sandy Ground by a Synthetic Aperture FM-CW Radar (Special Issue on Radar Technology)
- Special Section of Selected Papers from the 9th Karuizawa Workshop on Circuits and Systems
- A Mobility Model in 3-Dimensional PCS Indoor Environments (無線ネットワ-クの性能評価論文)
- FOREWORD (Special Section of Papers Selected from 1995 Joint Technical Conference on Circuits/Systems, Computers and Communications (JTC-CSCC'95))
- Proportion of Transformation Superplasticity and Expansion on Stress Releasement
- Effect of Alloying Elements and Transformation Temperature on Stress Releasement : Stress Releasement by Transformation Superplasticity (Part 2)
- Transient Characteristics of Mobile Communication Traffic in a Band-Shaped Service Area (Special Section on JTC-CSCC '92)
- Automatic Generation of Java-Based, Database-Independent Query API
- Automatic Generation of Java-Based, Database-Independent Query API
- BS-6-9 A Consideration of Message Spreading Pattern in Delay Tolerant Network(BS-6. Planning, Control and Management on Networks and Services)
- A Dynamic Channel Assignment Approach to Reuse Partitioning Systems Using Rearrangement Method
- A Flexible Hybrid Channel Assignment Strategy Using an Artificial Neural Network in a Cellular Mobile Communication System
- A Routing Protocol for Considering the Time Variant Mobility Model in Delay Tolerant Network