Realization of flow networks from non-terminal capacity matrices

Author

Tamura, Hiroshi ; Sengoku, Masakazu ; Shinoda, Shoji ; Abe, Takeo

Author_Institution

Dept. of Inf. & Electron. Eng., Niigata Univ., Japan

fYear

1998

fDate

24-27 Nov 1998

Firstpage

467

Lastpage

470

Abstract

In this paper, we consider a realization problem of an undirected flow network N from a matrix M. We assume that M is not always a terminal capacity matrix. In this condition, we consider a problem to minimize differences between capacities between vertex pairs in N, and elements of M. And we propose a method to construct N. Next, we consider a problem to minimize the number of such vertex pairs. Then, we show the problem is NP-hard

Keywords

computational complexity; graph theory; matrix algebra; network analysis; NP-hard problem; nonterminal capacity matrices; undirected flow network; vertex pairs; Network theory (graphs); Sufficient conditions; Symmetric matrices; Tree graphs; Upper bound;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 1998. IEEE APCCAS 1998. The 1998 IEEE Asia-Pacific Conference on

Conference_Location

Chiangmai

Print_ISBN

0-7803-5146-0

Type

conf

DOI

10.1109/APCCAS.1998.743825

Filename

743825

Link To Document

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2535201