Details

Autor(en) / Beteiligte

• Wanke, Egon

Titel

k-NLC graphs and polynomial algorithms

Ist Teil von

• Discrete Applied Mathematics, 1994-10, Vol.54 (2), p.251-266

Ort / Verlag

Elsevier B.V

Erscheinungsjahr

1994

Link zum Volltext

Quelle

Elsevier Journal Backfiles on ScienceDirect (DFG Nationallizenzen)

Beschreibungen/Notizen

• 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.