Feasible edge colorings of trees with cardinality constraints (Q1579549)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1506818
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Feasible edge colorings of trees with cardinality constraints |
scientific article; zbMATH DE number 1506818 |
Statements
Feasible edge colorings of trees with cardinality constraints (English)
0 references
28 June 2001
0 references
The following two extensions of the well-known regular edge colouring are considered. The first imposes cardinality constraints by fixing the number of times each colour can be used and the second restricts the set of possible colours that each edge can receive. The authors prove that both extensions are polynomially solvable for trees with maximum degree bounded by a constant. It is known that determining whether a given graph has an edge colouring satisfying the above constraints is a NP-complete problem, even if restricted to general bipartite multigraphs.
0 references
cost
0 references
timetabling
0 references
edge colouring
0 references
cardinality constraints
0 references
0.8026946783065796
0 references
0.7915429472923279
0 references
0.7850531339645386
0 references
0.7847449779510498
0 references
0.7799237966537476
0 references
