zbMATH — the first resource for mathematics

Maximum independent, minimally redundant sets in series-parallel graphs. (English) Zbl 0794.05124
Let \(G\) be a graph. The authors introduce a new graph invariant, \(\text{BIT}(G)\), the minimum total redundance of a maximum independent set. The invariant is defined to be the minimum value of \(\Sigma(1+\deg(v))\), \(v\in W\), over all maximum independent sets \(W\) of \(G\). They show that the problem whether \(\text{BIT}(G)> k\) is NP-hard.

05C99 Graph theory
Full Text: DOI
[1] Arnborg A., Linear-time algorithms for Np-hard problems restricted to partial Is-trees, TRITA-NA-8404 (1984) · Zbl 0527.68049
[2] Bange D. W., Congressus Numerantium 21 pp 101– (1978)
[3] Bange D. W., Sandia Laboratories Report, SAND 78–1087J (1978)
[4] Bance D. W., Applications of Discrete Mathematics, SIAM pp 189– (1988)
[5] Bern M. W., 26th Annual Symposium on the Foundations of Computer Science, Portland, OR pp 117– (1985)
[6] DOI: 10.1002/jgt.3190030306 · Zbl 0418.05049
[7] Borie R. B., Automatic generation of linear algorithms from predicate calculus descriptions of problems on recursively constructed graph families (1988)
[8] Cockayne E. J., IEEE Trans. Circuits and Systems Cas-22 pp 855– (1975)
[9] Dewdney A. K., Fast Turing reductions between problems in NP, Chapter 4: Reductions between NP-complete problems (1981)
[10] DOI: 10.1016/0304-3975(76)90059-1 · Zbl 0338.05120
[11] Garey, M. R., Johnson, D. S. and Tarjan, R. E. 1976. unpublished
[12] Garey M. R., Computers and Intractability (1979) · Zbl 0411.68039
[13] Grinstead D. L., Fractional domination and fractional packing in graphs, presented at the Nineteenth Southeastern Conference on Combinatorics, Graph Theory and Computing, Baton Rouge, La, 1988, to appear in Congressus Numerantium
[14] Grinstead D. L., A recurrence template for several domination related parameters in series-parallel graphs · Zbl 0812.68099
[15] Grinstead D. L., Annals of Discrete Math
[16] Grinstead D. L., Proc. 6th International Conf. on the Theory and Applications of Graphs
[17] Hare E., Discrete Algorithms and Complexity pp 437– (1987)
[18] Hedetniemi S. T., Proc. 250th Anniversary Conf. on Graph Theory, Fort Wayne, IN, March, 1986
[19] Karp, R. M. 1972.Reducibility among combinatorial problems, in Complexity of Computer ComputationsEdited by: Miller, R. E. and Thatcher, J. W. 85–103. New York: Plenum Press.
[20] DOI: 10.1016/0166-218X(83)90003-3 · Zbl 0507.05060
[21] Knuth, D. E. 1968.The Art of Computer Programming, Vol. 1: Fundamental Algorithms334–338. Reading: Addison-Wesley.
[22] DOI: 10.1016/0196-6774(86)90023-4 · Zbl 0611.05017
[23] Selig W. J., Proc. of the Sixth International Conf. on the Theory and Applications of Graphs
[24] Takamizawa K., J. Assoc. Comput. Mach. 29 pp 623– (1982)
[25] DOI: 10.1137/0201010 · Zbl 0251.05107
[26] Wimer T. V., Linear algorithms on k-terminal graphs (1987) · Zbl 0669.05050
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.