The p-Collection Problem in a Flow Network with Lower Bounds (Special Section on Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
In this paper we extend the p-collection problem to a flow network with lower bounds, and call the extended problem the lower-bounded p-collection problem. First we discuss the complexity of this problem to show NP-hardness for a network with path structure. Next we present a linear time algorithm for the lower-bounded 1-collection problem in a network with tree structure, and a pseudo-polynomial time algorithm with dynamic programming type for the lower-bounded p-collection problem in a network with tree structure. Using the pseudo-polynomial time algorithm, we show an exponential algorithm, which is efficient in a connected network with few cycles, for the lower-bounded p-collection problem.
- 社団法人電子情報通信学会の論文
- 1997-04-25
著者
-
Nakano K
Dept. Of Information Engineering Niigata University
-
Nakano Keisuke
Niigata Univ. Niigata‐shi Jpn
-
Nakano K
Niigata Univ. Niigata‐shi Jpn
-
SENGOKU Masakazu
Dept. of Information Engineering, Niigata University
-
WATANABE Kaoru
The author is with Osaka Electro-Communication University
-
NAKANO Keisuke
Graduate School of Science and Technology, Niigata 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
-
Nakano Keisuke
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
-
Nakano Keisuke
Department Of Information Engieering Niigata University
-
Nakano Keisuke
Niigata College Of Technology
-
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
-
Tamura Hiroshi
Graduate School Of Frontier Biosciences Osaka University Laboratory For Cognitive Neuroscience
-
中野 敬介
Graduate School of Science and Technology, Niigata University
関連論文
- Periodontal Tissue Reaction to Mechanical Stress in Mice
- Gene expression of matrix proteins in Cbfal- knockout mice(2nd ASIAN SCIENCE SEMINAR IN OKAYAMA 2003)
- 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)
- Boson Gas Mean Field Model Trapped by Weak Harmonic Potentials in Mesoscopic Scaling (Applications of Renormalization Group Methods in Mathematical Sciences)
- Histopathological Study of Matrix Mineralization by Osteoblastic-like and Odontoblastic-like Cells in Diffusion Chamber
- Localization of type IV collagen alpha chains in tooth germ development(International Symposium of Maxillofacial and Oral Regenerative Biology in Okayama 2005)
- Aging and Ectopic Bone Formation Induced by Partially Purified Bone Morphogenetic Protein : Blood Vessel Ingrowth and Localization of Type I Collagen and Osteocalcin Assessed by Immunohistochemistry
- Immunohistochemical Study of Cytokeratin Patterns in Follicular and Plexiform Ameloblastoma
- Gene Expression of Bone Matrix Protein mRNA during BMP Induced Chondrogenesis and Osteogenesis by in situ Hybridization
- A Study about Tooth Size and Arch Width Measurement
- Periodontal tissue reaction to mechanical stress in mice(Poster Session,The 16th Annual Meeting of the Society for Hard Tissue Regenerative Biology in Matsumoto Dental University)
- Development of CaTiO_3-C coating material for dental implant(5th Asian Science Seminar,Session 1)
- 14. Distribution pattern of αl(IV)- α6(IV)chains of type IV collagen in tooth germ morphogenesis(8th Annual Meeting of the Society of Hard Tissue Biology July 24, 1999 in Asahikawa)
- 13. Bone Augmentation by BMP-Collagen composite in calvarial subperiosteum of matured rats.
- 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)
- Special Section on Multi-dimensional Mobile Information Networks
- 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)
- 12. Gene expressions of bone and cartilage matrix proteins during ectopic hard tissue formation induced by BMP.
- 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)
- 15. Natural bovine bone morphogenetic protein (BMP) induces cytological and functional differentiation of preodontoblasts in vitro.
- 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
- Expression of Hsp70 in Acute Lung Injury Induced by Lipopolysaccharide
- 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
- Quantitative analysis of functional clustering of neurons in the macaque inferior temporal cortex
- Visual response properties of presumed inhibitory neurons in the macaque inferior temporal cortex
- A Routing Protocol for Considering the Time Variant Mobility Model in Delay Tolerant Network