A Minimal-State Processing Search Algorithm for Graph Coloring Problems
スポンサーリンク
概要
- 論文の詳細を見る
This paper presents a heuristic graph coloring algorithm named MIPS_CLR, a MInimal-state Processing Search algorithm for the graph CoLoRing problem. Given a graph G(V, E), the goal of this NP-complete problem is to find a color assignment to every vertex in V such that any pair of adjacent vertices must not receive the same color but also the total number of colors should be minimized. The graph coloring problem has been widely studied due to its large number of practical applications in various fields. In MIPS_CLR, a construction stage first generates an intial minimal state composed of as many as colored vertices by a simple greedy algorithm, after a miximal clique of G is found by a maximum clique algorithm. Then, a refinement stage iteratively seeks a solution state while keeping minimality in terms of a cost function by a minimal-state transition method. In this method, the schemes of a best color selection, a random color selection, a color assignment shuffle, and a gradual color expansion are used together to realize the discrete descent search with hill-climbing capabilities. The performance of MIPS_CLR is evaluated through solving DIMACS benchmark graph instances, where the solution quality is generally better than existing algorithms while the computation time is comparable with the best existing one. In particular, MIPS_CLR provides new lower bound solutions for several instances. The simulation results confirm the extensive search capability of our MIPS_CLR approach for the graph coloring problem.
- 社団法人電子情報通信学会の論文
- 2000-07-25
著者
-
Higashino Teruo
Department Of Informatics And Mathematical Science Osaka University
-
Higashino Teruo
The Department Of Informatics And Mathematical Science Graduate School Of Engineering Science Osaka
-
Funabiki Nobuo
The Department Of Informatics And Mathematical Science Graduate School Of Engineering Science Osaka
関連論文
- A WDS Clustering Algorithm for Wireless Mesh Networks
- An Optical-Drop Wavelength Assignment Algorithm for Efficient Wavelength Reuse under Heterogeneous Traffic in WDM Ring Networks(Discrete Mathematics and Its Applications)
- A Minimum Dead Space Algorithm for Generalized Isochronous Channel Reuse Problems in DQDB Networks(Network)
- P2PMM_router : A Two-Stage Heuristic Algorithm to Peer-to-Peer Multicast Routing Problems in Multihome Networks(Discrete Mathematics and Its Applications)
- A Quasi-Solution State Evolution Algorithm for Channel Assignment Problems in Cellular Networks(Special Section on Discrete Mathematics and Its Applications)
- Time-Action Alternating Model for Timed Processes and Its Symbolic Verification of Bisimulation
- A Proposal of Optimal Path Selection Algorithm for Static and Mobile Multicast Routing Problems
- Deriving Concurrent Synchronous EFSMs from Protocol Specifications in LOTOS (Special Section on Selected Papers from the 11th Workshop on Circuits and Systems in Karuizawa)
- A Method to Convert Concurrent EFSMs with Multi-Rendezvous into Synchronous Sequential Circuit(Special Section on Concurrent Systems Technology)
- Execution Time Analysis for Binary Code Executed on a Pipelined Processor Using Parametric Model Checking
- Relaxation of Coefficient Sensitiveness to Performance for Neural Networks Using Neuron Filter through Total Coloring Problems
- A Proposal of Neuron Filter: A Constraint Resolution Scheme of Neural Networks for Combinatorial Optimization Problems
- A Digital Neural Network for Multilayer Channel Routing with Crosstalk Minimization
- A Massive Digital Neural Network for Total Coloring Problems
- A Minimal-State Processing Search Algorithm for Graph Coloring Problems
- A Binary Neural Network Approach for Link Activation Problems in Multihop Radio Networks
- A Neural-Greedy Combination Algorithm for Board-Level Routing in FPGA-Based Logic Emulation Systems(Special Section on Discrete Mathematics and Its Applications)