zbMATH — the first resource for mathematics

A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound. (English) Zbl 0585.05032
Authors’ abstract: ”We introduce a notion of \(\lambda\)-extendible property of graphs and prove: If P is a \(\lambda\)-extendible property \((0<\lambda <1)\), then for a connected graph \(G=(V,E)\) and an objective function \(c: E\to R^+\) one can construct a spanning subgraph \(H=(V,F)\) which has the property P and satisfies \(c(F)=\lambda \cdot c(E)+1/2(1- \lambda)c(T),\) where c(T) is the weight of a minimal spanning tree (V,T) of G. Using the result one can construct e.g. large bipartite, balanced or acyclic subgraphs.”
Reviewer: Z.Ma

05C99 Graph theory
Full Text: DOI
[1] Barahona, F.; Grötschel, M.; Mahjoub, A.R., Facets of the bipartite subgraph polytope, Math. oper. res., 10, (1985) · Zbl 0578.05056
[2] Edmonds, J.; Karp, R.M., Theoretical improvements in algorithmic efficiency for network flow problems, Jacm, 19, 248-264, (1972) · Zbl 0318.90024
[3] Edwards, C.S., Some extremal properties of bipartite subgraphs, Canad. J. math., 25, 475-485, (1973) · Zbl 0254.05116
[4] Edwards, C.S., An improved lower bound for the number of edges in a largest bipartite subgraph, (), 167-181 · Zbl 0326.05115
[5] Garey, M.R.; Johnson, D.S.; Stockmayer, L., Some simflified NP-complete graph problems, Theoret. comput. sci., 1, 237-267, (1976) · Zbl 0338.05120
[6] Grötschel, M.; Pulleyblank, W.R., Weakly bipartite graphs and the MAX-cut problem, Oper. res. lett., 1, 23-27, (1981) · Zbl 0494.90078
[7] Nishizeki, T.; Ogawa, H.; Saito, N., Computational complexity of k-maximal cuts, (), 567-576
[8] Paton, K., An algorithm for the blocks and cutnodes of a graph, Comm. ACM, 14, 468-476, (1971) · Zbl 0223.94018
[9] Poljak, S.; Turzík, D., A polynomial algorithm for constructing a large bipartite subgraph, with an application to a satisfactory problem, Canad. J. math., 34, 519-524, (1982) · Zbl 0471.68041
[10] Sahni, S.; Gonzalez, T., P-complete approximate problems, Jacm, 23, 3, 555-565, (1976) · Zbl 0348.90152
[11] Spencer, J., Optimal ranking of tournaments, Networks, 1, 45-47, (1971) · Zbl 0236.05110
[12] Tarjan, R., Depth-first search and linear graph algorithms, SIAM J. comput., 1, 146-160, (1972) · Zbl 0251.05107
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.