Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
International Journal of Machine Learning and Cybernetics
Erschienen in: International Journal of Machine Learning and Cybernetics 2/2012

01.06.2012 | Original Article

Simulated annealing with stochastic local search for minimum dominating set problem

verfasst von: Abdel-Rahman Hedar, Rashad Ismail

Erschienen in: International Journal of Machine Learning and Cybernetics | Ausgabe 2/2012

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In this paper, we propose a new method based on simulated annealing (SA) to solve the minimum dominating set problem. To deal with the considered problem, a stochastic local search (SLS) method is built first to find local solutions next to given solutions. Then, a simulated annealing algorithm is invoked to enhance the SLS method with the ability of escaping from local solutions. Moreover, three trial solution generation mechanisms are used to improve iterate solutions. The experimental results have shown the promising performance of the proposed SA-based method in comparison with some other meta-heuristics in terms of solution qualities and computational costs.
Vorheriger Artikel Non-Parametric Kernel Learning with robust pairwise constraints
Nächster Artikel A robust framework for face contour detection from clutter background

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Weitere Produktempfehlungen anzeigen
Literatur
1.
Aarts E, Korst J (2000) Selected topics in simulated annealing. In: Ribeiro C, Hansen P (eds) Essays and surveys in metaheuristics. Kluwer, Boston, pp 1–38
2.
Alber J, Betzler N, Niedermeier R (2006) Experiments on data reduction for optimal domination in networks. Ann Oper Res 146(1):105–117MathSciNetMATHCrossRef
3.
Alkhalifah Y, Wainwright RL (2004) A genetic algorithm applied to graph problems involving subsets of vertices. In: IEEE congress on evolutionary computation 2004 (CEC’04). IEEE, pp 303–308
4.
Bettstetter C (2002) On the minimum node degree and connectivity of a wireless multihop network. In: Proceedings of the international symposium on mobile ad hoc networking and computing (MOBIHOC 02). ACM, New York, pp 80–91
5.
Burke E, Kendall G (2005) Search methodologies: introductory tutorials in optimization and decision support techniques. Springer, BerlinMATH
6.
Carey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, New York
7.
Cooper C, Klasing R, Zito M (2005) Lower bounds and algorithms for dominating sets in web graphs. Internet Math 2(3):275–300MathSciNetMATHCrossRef
8.
Fomin F, Grandoni F, Kratsch D (2005) Measure and conquer: domination a case study. In: Grefenstette J (ed) Proceedings of the 32nd international colloquium on automata, languages and programming, ICALP 2005. Lecture notes in computer science. Springer Verlag, pp 191–203
9.
Fomin F, Thilikos D (2006) Dominating sets in planar graphs: branch-width and exponential speed-up. SIAM J Comput 36(2):281–309MathSciNetMATHCrossRef
10.
Fomin FV, Kratsch D, Woeginger GJ (2004) Exact (exponential) algorithms for the dominating set problem. In: Hromkovic J, Nagl M, Westfechtel B (eds) Proceedings 30th international workshop on graph-theoretic concepts in computer science WG 2004. Lecture notes in computer science. Springer, pp 245–256
11.
Garcia S, Fernandez A, Luengo J, Herrera F (2009) A study of statistical techniques and performance measures for genetics-based machine learning: accuracy and interpretability. Soft Comput 13:959–977CrossRef
12.
13.
Haynes T, Hedetniemi S, Hedetniemi S, Henning M (2002) Domination in graphs applied to electric power networks. SIAM J Discrete Math 15(4):519–529MathSciNetMATHCrossRef
14.
Haynes T, Hedetniemi S, Slater P (1998) Domination in graphs, monographs and textbooks in pure and applied mathematics. Marcel Dekker, Inc., New York
15.
Haynes T, Hedetniemi S, Slater P (1998) Fundamentals of domination in graphs, monographs and textbooks in pure and applied mathematics. Marcel Dekker, Inc., New York
16.
Hedar A, Fukushima M (2002) Hybrid simulated annealing and direct search method for nonlinear unconstrained global optimization. Optim Methods Softw 17:891–912MathSciNetMATHCrossRef
17.
Hedar A, Fukushima M (2004) Heuristic pattern search and its hybridization with simulated annealing for nonlinear global optimization. Optim Methods Softw 19:291–308MathSciNetMATHCrossRef
18.
Hedar A, Fukushima M (2006) Derivative-free filter simulated annealing method for constrained continuous global optimization. J Glob Optim 35:521–549MathSciNetMATHCrossRef
19.
Hedar A, Ismail R (2010) Hybrid genetic algorithm for minimum dominating set problem. In: Taniar T et al (eds) ICCSA (4) 2010. Lecture notes in computer science. Springer, Berlin, pp 457–467
20.
Ho C, Ewe H (2005) A hybrid ant colony optimization approach (haco) for constructing load-balanced clusters. In: Grefenstette JJ (ed) IEEE congress on evolutionary computation, Edinburgh, UK. IEEE, pp 2010–2017
21.
Ho C, Singh Y, Ewe H (2006) An enhanced ant colony optimization metaheuristic for the minimum dominating set problem. Appl Artif Intell 20(10):881–903CrossRef
22.
Jovanovic R, Tuba M, Simian D (2010) Ant colony optimization to minimum weight dominating set problem. In: Proceedings of the 12th WSEAS international conference control, modeling and simulation on automatic control, Catania, Italy, pp 322–326
23.
24.
Korobitsyn D (1992) On the complexity of determining the domination number in monogenic classes of graphs. Discrete Math Appl 2(2):191–199MathSciNetCrossRef
25.
Lozin V, Milanic M (2006) Domination in graphs of low degree. RUTCOR Research Report (RRR), Rutgers University, New Jersey, vol 27, pp 1–11
26.
Lu G, Zhou M, Tang Y, Zhao M, Niu X, She K (2009) Approximation algorithms for the connected dominating set problem in unit disk graphs. J Electron Sci Technol China 7(3):214–222
27.
28.
Misra R, Mandal C (2010) Minimum connected dominating set using a collaborative cover heuristic for ad hoc sensor networks. IEEE Trans Parallel Distrib Syst 21(3):292–302CrossRef
29.
Muller H, Brandstadt A (1987) Np-completeness of Steiner tree and dominating set for chordal bipartite graphs. Theor Comput Sci 53(2):257–265MathSciNetCrossRef
30.
Parekh AK (1991) Analysis of a greedy heuristic for finding small dominating sets in graphs. Inf Process Lett 39(5):237–240MathSciNetMATHCrossRef
31.
Rego C, Alidaee B (2005) Metaheuristic optimization via memory and evolution, Tabu search and scatter search. Springer, BerlinMATH
32.
Rooij JV, Bodlaender H (2008) Design by measure and conquer, a faster exact algorithm for dominating set. In: Symposium on theoretical aspects of computer science 2008 (Bordeaux). Institute of Information and Computing Sciences, Utrecht University, pp 657–668
33.
Samuel H, Zhuang W (2009) Dtn based dominating set routing for manet in heterogeneous wireless networking. Mobile Netw Appl 14(2):154–164CrossRef
34.
35.
Sheskin D (2003) Handbook of parametric and nonparametric statistical procedures. CRC Press, Boca RatonCrossRef
36.
Torkestani J, Meybodi M (2010) An intelligent backbone formation algorithm for wireless ad hoc networks based on distributed learning automata. J Comput Netw 54(5):826–843MATHCrossRef
37.
Wan P, Alzoubi K, Frieder O (2003) A simple heuristic for minimum connected dominating set in graphs. Int J Found Comput Sci 14(2):323–333MathSciNetMATHCrossRef
38.
Zou F, Wang Y, Xuc X, Li X, Du H, Wan P, Wu W (2011) New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs. J Theor Comput Sci 412(3):198–208MATHCrossRef
Metadaten
Titel
Simulated annealing with stochastic local search for minimum dominating set problem
verfasst von
Abdel-Rahman Hedar
Rashad Ismail
Publikationsdatum
01.06.2012
Verlag
Springer-Verlag
Erschienen in
International Journal of Machine Learning and Cybernetics / Ausgabe 2/2012
Print ISSN: 1868-8071
Elektronische ISSN: 1868-808X
DOI
https://doi.org/10.1007/s13042-011-0043-y

Weitere Artikel der Ausgabe 2/2012

International Journal of Machine Learning and Cybernetics 2/2012 Zur Ausgabe

Original Article

Event ontology reasoning based on event class influence factors

Original Article

Decision function estimation using intelligent gravitational search algorithm

Original Article

Combining partially global and local characteristics for improved classification

Original Article

A robust framework for face contour detection from clutter background

Original Article

Non-Parametric Kernel Learning with robust pairwise constraints

Original Article

Handwritten character recognition using wavelet energy and extreme learning machine

Neuer Inhalt

    Bildnachweise