Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(4)
Complete Graph
Graph Coloring
List Coloring
Polynomial Algorithm
Subscribe
Academic
Publications
Some results on a trading model in a consensus list coloring
Some results on a trading model in a consensus list coloring,10.1109/INFTECH.2008.4621644,Damain Bogdanowicz,Krzysztof Giaro
Edit
Some results on a trading model in a consensus list coloring
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Damain Bogdanowicz
,
Krzysztof Giaro
Let S(v) denote a nonempty set of integers assigned to vertex v of graph G = (V, E). Let us call S a list assignment for G. We look for a legal
graph coloring
f such that for every vertex v isin V we have f(v) isin S(v). A trade from a vertex u to v means that we remove color c from S(u) and add it to S(v). In the trading model we ask how many trades are required in order to obtain a list assignment that has a list coloring. So (G, S) is ptradeable if this can be done in p or fewer trades. We show a
polynomial algorithm
for determining the minimal p for complete graphs. An analogous problem for trees is NPhard. However, it is polynomial for partial ktrees with fixed k and fixed total number of colors.
Conference:
International Conference on Information Technology  IT
, 2008
DOI:
10.1109/INFTECH.2008.4621644
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
ieeexplore.ieee.org
)
(
ieeexplore.ieee.org
)
Citation Context
(1)
...Graph coloring model has been used effectively for spectrum assignment in the network where centralized structure to assignment is not feasible such as in distributed network or opportunistic access network [
7
][11], which is similar to the problem of carrier assignment in downlink CoMP with CA to some extent...
Hongliang Bian
,
et al.
An ICSGC algorithm for carrier assignment in downlink coordinated mult...
References
(9)
Restricted coloring models for timetabling
(
Citations: 22
)
Dominique De Werra
Journal:
Discrete Mathematics  DM
, vol. 165166, pp. 161170, 1997
On the complexity of a restricted listcoloring problem
(
Citations: 7
)
Moshe Dror
,
Gerd Finke
,
Sylvain Gravier
,
Wieslaw Kubiak
Journal:
Discrete Mathematics  DM
, vol. 195, no. 13, pp. 103109, 1999
Complexity of list coloring problems with a fixed total number of colors
(
Citations: 9
)
Sylvain Gravier
,
Daniel Kobler
,
Wieslaw Kubiak
Journal:
Discrete Applied Mathematics  DAM
, vol. 117, no. 13, pp. 6579, 2002
Generalized Coloring for Treelike Graphs
(
Citations: 41
)
Klaus Jansen
,
Petra Scheffler
Journal:
Discrete Applied Mathematics  DAM
, vol. 75, no. 2, pp. 135155, 1997
Algorithmic complexity of list colorings
(
Citations: 26
)
Jan Kratochvíl
,
Zsolt Tuza
Journal:
Discrete Applied Mathematics  DAM
, vol. 50, no. 3, pp. 297302, 1994
Sort by:
Citations
(1)
An ICSGC algorithm for carrier assignment in downlink coordinated multipoint with carrier aggregation
Hongliang Bian
,
Caili Guo
,
Chunyan Feng
Conference:
IEEE International Conference on Network Infrastructure and Digital Content  ICNIDC
, 2010