loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
12th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'00)
Local minimum structures of graph-coloring problems for stochastic constraint satisfaction algorithms
Vancouver, British Columbia, Canada
November 13-November 15
ISBN: 0-7695-0909-6
ASCII Text
x 
 
F. Mizuno, S. Nishihara, "Local minimum structures of graph-coloring problems for stochastic constraint satisfaction algorithms," Tools with Artificial Intelligence, IEEE International Conference on, pp. 0366, 12th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'00), 2000.
 
 
BibTex
x
 
@article{ 10.1109/TAI.2000.889895,
author = {F. Mizuno and S. Nishihara},
title = {Local minimum structures of graph-coloring problems for stochastic constraint satisfaction algorithms},
journal ={Tools with Artificial Intelligence, IEEE International Conference on},
volume = {0},
year = {2000},
isbn = {0-7695-0909-6},
pages = {0366},
doi = {http://doi.ieeecomputersociety.org/10.1109/TAI.2000.889895},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Tools with Artificial Intelligence, IEEE International Conference on
TI - Local minimum structures of graph-coloring problems for stochastic constraint satisfaction algorithms
SN - 0-7695-0909-6
SP
EP
A1 - F. Mizuno,
A1 - S. Nishihara,
PY - 2000
KW - constraint theory; operations research; graph colouring; stochastic programming; local minimum structures; graph-coloring problems; stochastic constraint satisfaction; stochastic search algorithms; large-scale constraint satisfaction problems; locally minimal solutions; local constraint structures; local minima; graph-coloring problem; LM pair; stepwise refinement; hill-climbing
VL - 0
JA - Tools with Artificial Intelligence, IEEE International Conference on
ER -
 
F. Mizuno, Inst. of Inf. Sci. & Electron., Tsukuba Univ., Ibaraki, Japan
S. Nishihara, Inst. of Inf. Sci. & Electron., Tsukuba Univ., Ibaraki, Japan
Abstract: Many stochastic search algorithms developed to solve large-scale constraint satisfaction problems in a practical time have the drawback of becoming stuck in locally minimal solutions which are not acceptable as solutions. We analyze a stochastic search algorithm from the viewpoint of local constraint structures of local minima. Using the graph-coloring problem with three colors, we studied the local graph structures around which concurrent conflicts arise. We present a key constraint structure, an LM pair; which may make up a local minimum, clarifying the mechanism of how conflicted coloring in an LM pair hinders stepwise refinement of hill-climbing. Experimental results show that LM pairs are strongly correlated with the search efficiency of the stochastic search algorithm.
Index Terms:
constraint theory; operations research; graph colouring; stochastic programming; local minimum structures; graph-coloring problems; stochastic constraint satisfaction; stochastic search algorithms; large-scale constraint satisfaction problems; locally minimal solutions; local constraint structures; local minima; graph-coloring problem; LM pair; stepwise refinement; hill-climbing
Citation:
F. Mizuno, S. Nishihara, "Local minimum structures of graph-coloring problems for stochastic constraint satisfaction algorithms," ictai, pp.0366, 12th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'00), 2000
Usage of this product signifies your acceptance of the Terms of Use.