Is a Given Flow Uncontrollable? (Special Section on Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
An s-t flow in a directed network is called "uncontrollable", when the flow is representable as a positive sum of elementary s-t path flows. In this paper, we discuss the problem "Is a given flow uncontrollable?". We show that the problem is NP-complete.
- 一般社団法人電子情報通信学会の論文
- 1996-04-25
著者
-
Matsui Tomomi
University of Tokyo
-
Matsui T
Department Of Mathematical Engineering And Information Physics Faculty Of Engineering The University
-
Matsui Tomomi
Faculty Of Science And Engineering Chuo University
-
Matsui Tomomi
Department Of Mathematical Informatics Graduate School Of Information Science And Technology The Uni
-
Matsui Tomomi
Univ. Of Tokyo
-
Matsui Tomomi
The Authors Are With The Department Of Mathematical Informatics Graduate School Of Information Scien
-
Matsui Tomomi
Department Of Information And System Engineering Faculty Of Science And Engineering Chuo University
-
Matsui Tomomi
Department Of Mathematical Informatics Graduate School Of Information Science And Technology The Uni
関連論文
- LINEAR TIME APPROXIMATION ALGORITHM FOR MULTICOLORING LATTICE GRAPHS WITH DIAGONALS
- Improved Approximation Algorithms for Firefighter Problem on Trees
- Successful Manipulation in Stable Marriage Model with Complete Preference Lists
- 2-C-14 Cheating Strategies for Gale-Shapley Algorithm with Complete Preference Lists
- A note on Asymmetric Power Index for Voting Games
- A note on mixed level supersaturated designs
- Approximate Counting Scheme for m×n Contingency Tables(Foundations of Computer Science)
- Dependent Randomized Rounding to the Home-Away Assignment Problem in Sports Scheduling(Discrete Mathematics and Its Applications)
- Home-Away Table Feasibility Problem
- Notes on Equitable Round-Robin Tournaments(Special Section on Discrete Mathematics and Its Applications)
- Polynomial time approximate or perfect samplers for discretized Dirichlet distribution
- A Linear Relaxation for Hub Network Design Problems(Special Section on Discrete Mathematics and Its Applications)
- Linear Relaxation for Hub Network Design Problems
- DS-1-8 Randomized Approximation Scheme for Estimating Critical Path Length of Stochastic PERT Network
- 0.935-Approximation Randomized Algorithm for MAX 2SAT and Its Derandomization
- NEW APPROXIMATION ALGORITHMS FOR MAX 2SAT AND MAX DICUT
- Note on Equitable Round-Robin Tournaments
- A SURVEY OF ALGORITHMS FOR CALCULATING POWER INDICES OF WEIGHTED MAJORITY GAMES
- Is a Given Flow Uncontrollable? (Special Section on Discrete Mathematics and Its Applications)
- 3C2 INVERSE ASSIGNMENT PROBLEM FOR TIMETABLING IN TUTORING SCHOOL(Technical session 3C: OS2: Timetabling and assignment problems(2))
- Radiographic Progression of Silicosis among Japanese Tunnel Workers in Kochi