Distance graphs and the \(T\)-coloring problem (Q1297406)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Distance graphs and the \(T\)-coloring problem |
scientific article |
Statements
Distance graphs and the \(T\)-coloring problem (English)
0 references
27 February 2000
0 references
By the \(T\)-colouring problem we mean a generalized graph colouring problem which is one of the variants of the channel assignment problem in broadcast networks. The set \(T\) describes which channel distances are ``forbidden'' in order to prevent interference between transmitters. The \(T\)-colouring problem for complete graphs is equivalent to the clique problem for distance graphs. It is shown that (1) the \(T\)-colouring problem for complete graphs is NP-complete in the strong sense and (2) the ordered distance graphs can be recognized in polynomial time using linear programming techniques.
0 references
\(T\)-colouring problem
0 references
distance graphs
0 references
