EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
3921. Metaheuristics for Optimization on Graphs
Invited abstract in session WB-52: Parallel Optimization and Scalability, stream Combinatorial Optimization.
Wednesday, 10:30-12:00Room: 8003 (building: 202)
Authors (first author is the speaker)
| 1. | Tatjana Davidović
|
| Mathematical Institute of Serbian Academy of Sciences and Arts | |
| 2. | Dragan Stevanović
|
| Mathematical Institute, Serbian Academy of Sciences and Arts | |
| 3. | Predrag Djordjevic
|
| Mathematical Institute, Serbian Academy of Sciences and Arts | |
| 4. | Robert Doža
|
| Faculty of Mathematics, University of Belgrade | |
| 5. | Luka Radanovic
|
| Faclty of Mathematics, University of Belgrade | |
| 6. | Marko Milenkovic
|
| Faculty of Science and Mathematics, University of Nis | |
| 7. | Milica Andjelic
|
| Department of Mathematics, Kuwait University |
Abstract
Optimization problems on graphs involve the search for graphs of a given size that minimize or maximize a certain invariant or a combination of invariants. These problems are usually NP-hard and the exhaustive enumeration of all possibilities is not acceptable. Efficient dealing with these problems can help theoreticians to get some useful hints and make analytical proof out of these results. Computer-assisted proofs are common in the graph theory for a while now. Several dedicated software packages have been developed, such as AutoGraphiX (https://www.autographix.ca), newGraph (https://www.mi.sanu.ac.rs/newgraph/), PHOEG (https://phoeg.umons.ac.be/phoeg), to mention a few. They are, however, too general and in some cases could require unacceptably long CPU time to provide useful results. Another popular approach is to develop metaheuristic tailored for each particular optimization problem. We illustrate the application of Variable Neighborhood Search (VNS) metaheuristic to Spectral Reconstruction of Graphs and Maximization of Spectral Radius of Threshold Graphs. The proposed algorithms are tested on a representative set of test graphs. Conducted experimental evaluation shows the superiority of the proposed approach over the application of dedicated software. The work has been partially supported by the Scientific Fund of the Republic of Serbia, Grant LZWK.
Keywords
- Graphs and Networks
- Metaheuristics
- Software
Status: accepted
Back to the list of papers