main-content

## Weitere Artikel dieser Ausgabe durch Wischen aufrufen

10.07.2017 | Methodologies and Application | Ausgabe 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.

### 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
• 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
• 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
• 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

Zur Ausgabe