Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

10.07.2017 | Methodologies and Application | Ausgabe 19/2018

Soft Computing 19/2018

Improved integer linear programming formulation for weak Roman domination problem

Zeitschrift:
Soft Computing > Ausgabe 19/2018
Autor:
Marija Ivanović
Wichtige Hinweise
Communicated by V. Loia.

Electronic supplementary material

The online version of this article (doi:10.​1007/​s00500-017-2706-4) contains supplementary material, which is available to authorized users.
This research was partially supported by the Serbian Ministry of Education, Science and Technological Developments under the Grant No. TR36006.

Abstract

Let \(f:V \rightarrow \{0,1,2\}\) be a function, \(G=(V,E)\) be a graph with a vertex set V and a set of edges E and let the weight of the vertex \(u \in V\) be defined by f(u). A vertex u with property \(f(u)=0\) is considered to be defended with respect to the function f if it is adjacent to a vertex with positive weight. Further, the function f is called a weak Roman dominating function (WRDF) if for every vertex u with property \(f(u)=0\) there exists at least one adjacent vertex v with positive weight such that the function \(f':V \rightarrow \{0,1,2\}\) defined by \(f'(u)=1\), \(f'(v)=f(v)-1\) and \(f'(w)=f(w)\), \(w \in V \setminus \{u,v\}\) has no undefended vertices. In this paper, an optimization problem of finding the WRDF f such that \(\sum _{u \in V}{f(u)}\) is minimal, known as the weak Roman domination problem (WRDP), is considered. Therefore, a new integer linear programing (ILP) formulation is proposed and compared with the one known from the literature. Comparison between the new and the existing formulation is made through computational experiments on a grid, planar, net and randomly generated graphs known from the literature and up to 600 vertices. Tests were run using standard CPLEX and Gurobi optimization solvers. The obtained results demonstrate that the proposed new ILP formulation clearly outperforms the existing formulation in the sense of solutions’ quality and running times.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 30 Tage kostenlos.

Zusatzmaterial
Supplementary material 1 (pdf 2666 KB)
500_2017_2706_MOESM1_ESM.pdf
Supplementary material 2 (pdf 482 KB)
500_2017_2706_MOESM2_ESM.pdf
Supplementary material 3 (pdf 341 KB)
500_2017_2706_MOESM3_ESM.pdf
Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 19/2018

Soft Computing 19/2018 Zur Ausgabe

Premium Partner

    Bildnachweise