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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Neural Computing and Applications
Erschienen in: Neural Computing and Applications 1/2017

26.04.2016 | Original Article

A path cost-based GRASP for minimum independent dominating set problem

verfasst von: Yiyuan Wang, Ruizhi Li, Yupeng Zhou, Minghao Yin

Erschienen in: Neural Computing and Applications | Sonderheft 1/2017

Einloggen

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

search-config
loading …

Abstract

The minimum independent dominating set problem (MIDS) is an extension of the classical dominating set problem with wide applications. In this paper, we describe a greedy randomized adaptive search procedure (GRASP) with path cost heuristic for MIDS, as well as the classical tabu mechanism. Our novel GRASP algorithm makes better use of the vertex neighborhood information provided by path cost and thus is able to discover better and more solutions and to escape from local optimal solutions when the original GRASP fails to find new improved solutions. Moreover, to further overcome the serious cycling problem, the tabu mechanism is employed to forbid some just-removed vertices back to the candidate solution. Computational experiments carried out on standard benchmarks, namely DIMACS instances, show that our algorithm consistently outperforms two MIDS solvers as well as the original GRASP.
Vorheriger Artikel Online adaptive multiple pedestrian tracking in monocular surveillance video
Nächster Artikel -Hill climbing: an exploratory local search

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

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

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+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
Literatur
1.
Erciyes K, Dagdeviren O, Cokuslu D et al (2007) Graph theoretic clustering algorithms in mobile ad hoc networks and wireless sensor networks. Appl. Comput. Math 6(2):162–180MathSciNetMATH
2.
Chen Y, Liestman A, Liu J (2004) Clustering algorithms for ad hoc wireless networks. Ad Hoc and Sensor Networks 28:76
3.
Lin CR, Gerla M (1997) Adaptive clustering for mobile wireless networks. Selected Areas in Communications, IEEE Journal on 15(7):1265–1275CrossRef
4.
Nocetti FG, Gonzalez JS, Stojmenovic I (2003) Connectivity based k-hop clustering in wireless networks. Telecommunication systems 22(1–4):205–220CrossRef
5.
Basagni S (1999) Distributed clustering for ad hoc networks. In: Proceedings of the 1999 international symposium on parallel architectures, algorithms and networks. IEEE Computer Society, pp 310–315
6.
7.
Santos AC, Bendali F, Mailfert J et al (2009) Heuristics for designing energy-efficient wireless sensor network topologies. Journal of networks 4(6):436–444CrossRef
8.
Akyildiz IF, Kasimoglu IH (2004) Wireless sensor and actor networks: research challenges. Ad Hoc Netw 2(4):351–367CrossRef
9.
McLaughlan B, Akkaya K (2007) Coverage-based clustering of wireless sensor and actor networks. In: IEEE international conference on pervasive services. IEEE, pp 45–54
10.
Michael RG, David SJ (1979) Computers and intractability: a guide to the theory of NP-completeness. WH Freeman, San FranciscoMATH
11.
12.
Goddard W, Henning MA (2013) Independent domination in graphs: a survey and recent results. Discrete Mathematics 313(7):839–854MathSciNetCrossRefMATH
13.
Johnson DS, Yannakakis M, Papadimitriou CH (1988) On generating all maximal independent sets. Information Processing Letters 27(3):119–123MathSciNetCrossRefMATH
14.
15.
Gaspers S, Liedloff M (2006) A branch-and-reduce algorithm for finding a minimum independent dominating set in graphs. Graph-theoretic concepts in computer science. Springer, Berlin, pp 78–89MATH
16.
Liu C, Song Y (2006) Exact algorithms for finding the minimum independent dominating set in graphs. Algorithms and computation. Springer, Berlin, pp 439–448MATH
17.
Bourgeois N, Della Croce F, Escoffier B et al (2013) Fast algorithms for min independent dominating set. Discrete Applied Mathematics 161(4):558–572MathSciNetCrossRefMATH
18.
Cai SW, Su KL, Luo C et al (2013) Numvc: an efficient local search algorithm for minimum vertex cover. J Artif Intell Res 46:687–716MathSciNetMATH
19.
Huang P, Yin M (2014) An upper (lower) bound for max (min) CSP. Science China Information Sciences 57(7):1–9MathSciNetMATH
20.
Gao J, Wang J, Yin M (2015) Experimental analyses on phase transitions in compiling satisfiability problems. Science China Information Sciences 58(3):1–11CrossRef
21.
Li X, Yin M (2015) Modified Cuckoo search algorithm with self adaptive parameter method. Inf Sci 298:80–97CrossRef
22.
Wang YY, Ouyang DT, Zhang L et al (2015) A novel local search for unicost set covering problem using hyperedge configuration checking and weight diversity. Sci China Inf Sci. doi:10.​1007/​s11432-015-5377-8
23.
Wang YY, Cai SW, Yin MH (2016) Two efficient local search algorithms for maximum weight clique problem. In: AAAI
24.
Li X, Zhang J, Yin M (2014) Animal migration optimization: an optimization algorithm inspired by animal migration behavior. Neural Comput Appl 24(7–8):1867–1877CrossRef
25.
Li X, Wang J, Yin M (2014) Enhancing the performance of cuckoo search algorithm using orthogonal learning method. Neural Comput Appl 24(6):1233–1247CrossRef
26.
Li X, Yin M (2014) Self adaptive constrained Artificial Bee Colony for constrained numerical optimization. Neural Comput Appl 24(3–4):723–734CrossRef
27.
Li R, Hu S, Wang Y, Yin M A local search algorithm with tabu strategy and perturbation mechanism for generalized vertex cover problem. Neural Comput Appl. doi:10.​1007/​s00521-015-2172-9
28.
Festa P, Resende MGC (2002) GRASP: an annotated bibliography. Essays and surveys in metaheuristics. Springer, Berlin, pp 325–367CrossRefMATH
29.
Festa P, Resende MGC (2009) An annotated bibliography of GRASP–Part I: algorithms. International Transactions in Operational Research 16(1):1–24MathSciNetCrossRefMATH
30.
Festa P, Resende MGC (2009) An annotated bibliography of GRASP–Part II: applications. International Transactions in Operational Research 16(2):131–172MathSciNetCrossRefMATH
31.
Glover F (1997) Tabu search and adaptive memory programming—advances, applications and challenges. Interfaces in computer science and operations research. Springer, Berlin, pp 1–75MATH
32.
33.
34.
Johnson DS, Trick MA (1993) Cliques, coloring, and satisfiability: second DIMACS implementation challenge, vol 26. American Mathematical Society, ProvidenceMATH
35.
Aiex RM, Resende MGC, Ribeiro CC (2007) TTT plots: a perl program to create time-to-target plots. Optimization Letters 1:355–366MathSciNetCrossRefMATH
Metadaten
Titel
A path cost-based GRASP for minimum independent dominating set problem
verfasst von
Yiyuan Wang
Ruizhi Li
Yupeng Zhou
Minghao Yin
Publikationsdatum
26.04.2016
Verlag
Springer London
Erschienen in
Neural Computing and Applications / Ausgabe Sonderheft 1/2017
Print ISSN: 0941-0643
Elektronische ISSN: 1433-3058
DOI
https://doi.org/10.1007/s00521-016-2324-6

Weitere Artikel der Sonderheft 1/2017

Neural Computing and Applications 1/2017 Zur Ausgabe

Original Article

Local search algorithm with path relinking for single batch-processing machine scheduling problem

Original Article

Estimation of melting points of fatty acids using homogeneously hybridized support vector regression

Original Article

Constrained self-organizing feature map to preserve feature extraction topology

Original Article

Generalized self-tuning regulator based on online support vector regression

Original Article

Toward growing modular deep neural networks for continuous speech recognition

Correction

Correction to: pART2: using adaptive resonance theory for web caching prefetching