×

\(w\)-density and \(w\)-balanced property of weighted graphs. (English) Zbl 1016.05067

Summary: The notion of \(w\)-density for graphs with positive weights on vertices and nonnegative weights on edges is introduced. A weighted graph is called \(w\)-balanced if its \(w\)-density is no less than the \(w\)-density of any subgraph of it. In this paper, a good characterization of \(w\)-balanced weighted graphs is given. Applying this characterization, many large \(w\)-balanced weighted graphs are formed by combining smaller ones. In the case where a graph is not \(w\)-balanced, a polynomial-time algorithm to find a subgraph of maximum \(w\)-density is proposed. It is shown that the \(w\)-density theory is closely related to the study of games of sums of edge weights for graphs \(G= (V,E)\) with edge-weight function \(w: E\to\mathbb{R}\).

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C90 Applications of graph theory
05C99 Graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bondy, J. A., Murty, U. S. R., Graph Theory with Applications, Macmillan, London and Elsevier, New York, 1976. · Zbl 1226.05083
[2] Deng, X., Mathematical programming: Complexity and algorithms, Ph. D. Thesis, Department of Operations Research, Stanford University, California, 1989.
[3] Deng, X., Combinatorial optimization and coalition games, In: Du and Pardalos eds., Handbook of Combinatorial Optimization, Kluwer Academic Publishers, 1998, 1–27.
[4] Deng, X., Papadimitriou, C. H., On the complexity of cooperative solution concepts, Mathematics of Operations Research, 1994, 19(2):257–266. · Zbl 0824.90146 · doi:10.1287/moor.19.2.257
[5] Erdös, P., Rényi, A., On the evolution of random graphs, Publ. Math. Inst. Hung. Acad. Sci., 1960, 5: 17–61. · Zbl 0103.16301
[6] Karoński, M., A review of random graphs, J. Graph Theory, 1982, 6: 349–389. · Zbl 0512.05052 · doi:10.1002/jgt.3190060402
[7] Penrice, S.G., Balanced graphs and network flows, Networks, 1997, 29: 77–80. · Zbl 0888.90146 · doi:10.1002/(SICI)1097-0037(199703)29:2<77::AID-NET1>3.0.CO;2-8
[8] Picard, J. C., Queyanne, M., A network flow solution to some nonlinear 0–1 programming problems, with applications to graph theory, Networks, 1982, 12: 141–159. · Zbl 0485.90081 · doi:10.1002/net.3230120206
[9] Picard, J. C., Ratliff, H. D., Minimum cuts and related problems, Networks, 1974, 5: 357–370. · Zbl 0325.90047 · doi:10.1002/net.3230050405
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.