Distance graphs and the \(T\)-coloring problem (Q1297406)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Distance graphs and the \(T\)-coloring problem |
scientific article; zbMATH DE number 1321772
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Distance graphs and the \(T\)-coloring problem |
scientific article; zbMATH DE number 1321772 |
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
0 references
0 references
0 references
0.94910264
0 references
0 references
0.93475854
0 references
0 references
