×

zbMATH — the first resource for mathematics

\(k\)-NLC graphs and polynomial algorithms. (English) Zbl 0812.68106
Summary: We introduce the class of \(k\)-node label controlled (NLC) graphs and the class of \(k\)-NLC trees. Each \(k\)-NLC graph is an undirected tree- structured graph, where \(k\) is a positive integer. The class of \(k\)-NLC trees is a proper subset of the class of \(k\)-NLC graphs. Both classes include many interesting graph families. For instance, each partial \(k\)- tree is a \((2^{k+ 1}-1)\)-NLC tree and each co-graph is a 1-NLC graph. Furthermore, we introduce a very general method for the design of polynomial algorithms for NP-complete graph problems, where the input graphs are restricted to tree-structured graphs. We exemplify our method with the simple max-cut problem and the Hamiltonian circuit property on \(k\)-NLC graphs.

MSC:
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arnborg, S.; Corneil, D.G.; Proskurowski, A., Complexity of finding embeddings in a k-tree, SIAM J. algorithms discrete methods, 8, 2, 227-284, (1987) · Zbl 0611.05022
[2] Arnborg, S.; Lagergren, J.; Seese, D., Problems easy for tree-decomposable graphs, J. algorithms, 12, 308-340, (1991) · Zbl 0734.68073
[3] Bern, M.W.; Lawler, E.L.; Wong, A.L., Linear-time computation of optimal subgraphs of decomposable graphs, J. algorithms, 8, 216-235, (1987) · Zbl 0618.68058
[4] Bodlaender, H.L., Dynamic programming on graphs with bounded treewidth, (), 105-118, Lecture Notes in Computer Science
[5] Brandstädt, A., Special graph classes – a survey, Technical report SM-DU-199, (1991), Universität-Gesamthochschule-Duisburg Duisburg
[6] Burlet, M.; Uhry, J.P., Parity graphs, Ann. discrete math., 21, 253-277, (1984) · Zbl 0558.05036
[7] Courcelle, B., An axiomatic definition of context-free rewriting and its application to NLC graph grammars, Theoret. comput. sci., 55, 141-181, (1987) · Zbl 0644.68095
[8] Corneil, D.G.; Perl, Y.; Stewart, L.K., Cographs: recognition, applications, and algorithms, Proceedings of 15th southeastern conference on combinatories, graph theory, and computing, (1984) · Zbl 0563.05049
[9] Garey, M.R.; Johnson, D.S., Computers and intractability, A guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[10] Habel, A., Hyperedge replacement: grammars and languages, Lecture notes in computer science, 643, (1992), Springer Berlin · Zbl 0787.68066
[11] Janssens, D.; Rozenberg, G., On the structure of node label controlled graph languages, Inform. sci., 20, 191-216, (1980) · Zbl 0452.68073
[12] Janssens, D.; Rozenberg, G., Restrictions, extensions, and variations of NLC grammars, Inform. sci., 20, 217-244, (1989) · Zbl 0452.68074
[13] Janssens, D.; Rozenberg, G., Graph grammars with neighbourhood-controlled embedding, Theoret. comput. sci., 21, 55-74, (1982) · Zbl 0486.68075
[14] Rose, D.J., On simple characterization of k-trees, Discrete math., 7, 317-322, (1974) · Zbl 0285.05128
[15] Robertson, N.; Seymour, P.D., Graph minors II. algorithmic aspect of tree width, J. algorithms, 7, 309-322, (1986) · Zbl 0611.05017
[16] Sumner, P.D., Dacey graphs, J. austral. soc., 18, 492-502, (1974) · Zbl 0314.05108
[17] Tarjan, R.E.; Yannakakis, M., Simple linear-time algorithms to test chordality of graphs, acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. comput., 13, 566-579, (1984) · Zbl 0545.68062
[18] Bodlaender, H.L., A linear time algorithm for finding tree-decompositions of small treewidth, (), 226-234 · Zbl 1310.05194
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.