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

17.06.2016 | Original Article

GRASP for connected dominating set problems

verfasst von: Ruizhi Li, Shuli Hu, Jian Gao, Yupeng Zhou, Yiyuan Wang, 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 connected dominating set problem, a variant of the classical minimum dominating set problem, is a very significant NP-hard combinatorial optimization problem with a number of applications. To address this problem, a greedy randomized adaptive search procedure (GRASP) that incorporates a novel local search procedure based on greedy function and tabu strategy is proposed. Firstly, the greedy function is proposed to define the score of each vertex so that our algorithm could obtain different possible optimal solutions. Secondly, a tabu strategy is introduced to prevent the search trapping into the local minimum and avoid the cycling problems. The proposed algorithm is evaluated against several state-of-art algorithms on a large collection of benchmark instances. The experimental results prove that GRASP performs better than its competitors in most benchmark instances.
Vorheriger Artikel An effective combining classifier approach using tree algorithms for network intrusion detection
Nächster Artikel Adaptive tracking control for a class of non-affine switched stochastic nonlinear systems with unmodeled dynamics

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.
Berge C (1973) Graphs and hypergraphs[M]. North-Holland Publishing Company, AmsterdamMATH
2.
Liu CL (1968) Introduction to combinatorial mathematics[M]. McGraw-Hill, New YorkMATH
3.
Di Benedetto CA (2010) Diffusion of innovation. Wiley, Chichester
4.
Valente TW (1995) Network models of the diffusion of innovations. Hampton Press, Cresskill
5.
Domingos P, Richardson M (2001) Mining the network value of customers. In: Proceedings of the seventh ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 57–66
6.
Goldenberg J, Libai B, Muller E (2001) Using complex systems analysis to advance marketing theory development: modeling heterogeneity effects on new product growth through stochastic cellular automata. Acad Mark Sci Rev 9(3):1–18
7.
Asavathiratham C, Roy S, Lesieutre B et al (2001) The influence model. Control Syst IEEE 21(6):52–64CrossRef
8.
Cooper C, Klasing R, Zito M (2005) Lower bounds and algorithms for dominating sets in web graphs. Internet Math 2(3):275–300MathSciNetCrossRefMATH
9.
Eubank S, Guclu H, Kumar VSA et al (2004) Modelling disease outbreaks in realistic urban social networks. Nature 429(6988):180–184CrossRef
10.
Stanley EA (2006) Social networks and mathematical modeling. Connections 27(1):43–49
11.
Garey M, Johnson DS (1979) Computers and intractability, a guide to the theory of NP—completeness. Freeman, San FranciscoMATH
12.
Ruan L, Du H, Jia X, Wu W, Li Y, Ko KI (2004) A greedy approximation for minimum connected dominating sets. Theor Comput Sci 329(1–3):325–330MathSciNetCrossRefMATH
13.
Cheng X, Ding M, Chen D (2004) An approximation algorithm for connected dominating set in ad hoc networks. In: Proceedings of the international workshop on theoretical aspects of wireless ad hoc, sensor and peer-to-peer networks (TAWN)
14.
Min M, Du H, Jia X, Huang CX, Huang SCH, Wu W (2006) Improving construction for connected dominating set with Steiner tree in wireless sensor networks. J Glob Optim 35(1):111–119MathSciNetCrossRefMATH
15.
16.
Butenko S, Cheng X, Oliveira C, Pardalos P (2004) A new heuristic for the minimum connected dominating set problem on ad hoc wireless networks. In: Butenko S (Ed) Recent developments in cooperative control and optimization. Kluwer Academic Publishers, New York, pp 61–73
17.
Butenko S, Oliveira C, Pardalos P (2003) A new algorithm for the minimum connected dominating set problem on ad hoc wireless networks. In: CCCT’03. International Institute of Informatics and Systematics (IIIS), pp 39–44
18.
Gendron B, Lucena A, da Cunha AS et al (2014) Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem. INFORMS J Comput 26(4):645–657MathSciNetCrossRefMATH
19.
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
20.
Morgan M, Grout V (2007) Metaheuristics for wireless network optimisation. In: The third advanced international conference on telecommunications, AICT 2007, p 15, May 2007
21.
He H, Zhu Z, Makinen E (2009) A neural network model to minimize the connected dominating set for self-configuration of wireless sensor networks. IEEE Trans Neural Netw 20(6):973–982CrossRef
22.
Downey RG, Fellows MR, McCartin C, Rosamond FA (2008) Parameterized approximation of dominating set problems. Inf Process Lett 109(1):68–70MathSciNetCrossRefMATH
23.
Jovanovic R, Tuba M (2013) Ant colony optimization algorithm with pheromone correction strategy for the minimum connected dominating set problem. Comput Sci Inf Syst 10(1):133–149CrossRef
24.
Nimisha TS, Ramalakshmi R (2015) Energy efficient connected dominating set construction using ant colony optimization technique in wireless sensor network. In: Innovations in information, embedded and communication systems (ICIIECS), 2015 international conference on IEEE, 2015, pp 1–5
25.
Feo TA, Resende MGC (1989) A probabilistic heuristic for a computationally difficult set covering problem. Oper Res Lett 8:67–71MathSciNetCrossRefMATH
26.
27.
Resende MGC, Ribeiro CC (2002) Greedy randomized adaptive search procedures. In: Glover F, Kochenberger G (eds) Handbook of metaheuristics. Kluwer Academic Publishers, Norwell, pp 219–249
28.
Resende MGC, Ribeiro CC (2010) Greedy randomized adaptive search procedures: advances and applications. In: Gendreau M, Potvin J-Y (eds) Handbook of metaheuristics, 2nd edn. Springer, Berlin
29.
Festa P, Resende MGC (2002) GRASP: an annotated bibliography. In: Ribeiro CC, Hansen P (eds) Essays and surveys on metaheuristics. Kluwer Academic Publishers, Boston, pp 325–367CrossRef
30.
31.
32.
33.
Ho CK, Singh YP, Ewe HT (2006) An enhanced ant colony optimization metaheuristic for the minimum dominating set problem. Appl Artif Intell 20(10):881–903CrossRef
34.
Zhou Y, Zhang H, Li R, Wang J (2016) Two local search algorithms for partition vertex cover problem. J Comput Theor Nanosci 13:743–751CrossRef
35.
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
36.
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
37.
Li X, Yin M (2014) Self adaptive constrained Artificial Bee Colony for constrained numerical optimization. Neural Comput Appl 24(3–4):723–734CrossRef
38.
Wang Y, Cai S, Yin M (2016) Two efficient local search algorithms for maximum weight clique problem. In: AAAI2016
39.
Wang Y, Yin M, Ouyang D, Zhang L (2016) A novel local search algorithm with configuration checking and scoring mechanism for the set k-covering problem. Int Trans Oper Res. doi:10.​1111/​itor.​12280
40.
41.
Li R, Hu S, Wang Y, Yin M (2016) 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
42.
Zhang X, Li X, Wang J (2016) Local search algorithm with path relinking for single batch-processing machine scheduling problem. Neural Comput Appl. doi:10.​1007/​s00521-016-2339-z
43.
Li R, Hu S, Wang J (2015) The community structure of the constraint satisfaction problem instances of model RB. J Comput Theor Nanosci 12:6088–6093CrossRef
Metadaten
Titel
GRASP for connected dominating set problems
verfasst von
Ruizhi Li
Shuli Hu
Jian Gao
Yupeng Zhou
Yiyuan Wang
Minghao Yin
Publikationsdatum
17.06.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-2429-y

Weitere Artikel der Sonderheft 1/2017

Neural Computing and Applications 1/2017 Zur Ausgabe

Original Article

Forecasting the energy demand of Turkey with a NN based on an improved Particle Swarm Optimization

Original Article

Support top irrelevant machine: learning similarity measures to maximize top precision for image retrieval

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

Consensus of delayed multi-agent dynamical systems with stochastic perturbation via impulsive approach

Original Article

A novel learning algorithm of single-hidden-layer feedforward neural networks

Premium Partner

    Bildnachweise