Complementary approaches for the computation of the independent number of a graph

Maria do Carmo Proença Caseiro Brás

Complementary approaches for the computation of the independent number of a graph

DM - Departamento de Matemática

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

The problem of finding the independent number of an undirected graph is formulated as two equivalent Mathematical Programs with Linear Complementarity Constraints (MPLCC). A multistarting Lemke's method is introduced for dealing with the first formulation and is able to find a good approximate of the independent number in a finite number of iterations. A sequential complementary algorithm is also discussed for the second formulation and can find the independent number at least in theory. Some computational experience is included to highlight the efficacy of the complementary approaches for computing the independent number of graphs from the Dimacs collection.

Original language	Unknown
Title of host publication	Mathematics and Computers in Science and Engineering
Editors	C Bulucea, V Mladenov, E Pop, M Leba, N Mastorakis
Place of Publication	AG LOANNOU THEOLOGOU 17-23, 15773 ZOGRAPHOU, ATHENS, GREECE
Publisher	World Scientific and Engineering Acad and Soc
Pages	178-183
ISBN (Print)	978-960-474-138-0
Publication status	Published - 1 Jan 2009
Event	14th WSEAS International Conference on Applied Mathematics (MATH '09) - Puerto De La Cruz (Tenerife, Canary Islands), Spain Duration: 14 Sept 2009 → 16 Sept 2009

Conference

Conference	14th WSEAS International Conference on Applied Mathematics (MATH '09)
Country/Territory	Spain
City	Puerto De La Cruz (Tenerife, Canary Islands)
Period	14/09/09 → 16/09/09

Cite this

Brás, Maria do Carmo Proença Caseiro. / Complementary approaches for the computation of the independent number of a graph. Mathematics and Computers in Science and Engineering. editor / C Bulucea ; V Mladenov ; E Pop ; M Leba ; N Mastorakis. AG LOANNOU THEOLOGOU 17-23, 15773 ZOGRAPHOU, ATHENS, GREECE : World Scientific and Engineering Acad and Soc, 2009. pp. 178-183

@inproceedings{111431803e724c68bb869140e448f502,

title = "Complementary approaches for the computation of the independent number of a graph",

abstract = "The problem of finding the independent number of an undirected graph is formulated as two equivalent Mathematical Programs with Linear Complementarity Constraints (MPLCC). A multistarting Lemke's method is introduced for dealing with the first formulation and is able to find a good approximate of the independent number in a finite number of iterations. A sequential complementary algorithm is also discussed for the second formulation and can find the independent number at least in theory. Some computational experience is included to highlight the efficacy of the complementary approaches for computing the independent number of graphs from the Dimacs collection.",

keywords = "Linear Complementarity Problems, Graph Theory, Global Optimization, Nonlinear Programming",

author = "Br{\'a}s, {Maria do Carmo Proen{\c c}a Caseiro}",

note = "14th WSEAS International Conference on Applied Mathematics, Puerto de la Cruz, SPAIN, DEC 14-16, 2009; 14th WSEAS International Conference on Applied Mathematics (MATH '09) ; Conference date: 14-09-2009 Through 16-09-2009",

year = "2009",

month = jan,

day = "1",

language = "Unknown",

isbn = "978-960-474-138-0",

pages = "178--183",

editor = "C Bulucea and V Mladenov and E Pop and M Leba and N Mastorakis",

booktitle = "Mathematics and Computers in Science and Engineering",

publisher = "World Scientific and Engineering Acad and Soc",

}

Brás, MDCPC 2009, Complementary approaches for the computation of the independent number of a graph. in C Bulucea, V Mladenov, E Pop, M Leba & N Mastorakis (eds), Mathematics and Computers in Science and Engineering. World Scientific and Engineering Acad and Soc, AG LOANNOU THEOLOGOU 17-23, 15773 ZOGRAPHOU, ATHENS, GREECE, pp. 178-183, 14th WSEAS International Conference on Applied Mathematics (MATH '09), Puerto De La Cruz (Tenerife, Canary Islands), Spain, 14/09/09.

Complementary approaches for the computation of the independent number of a graph. / Brás, Maria do Carmo Proença Caseiro.
Mathematics and Computers in Science and Engineering. ed. / C Bulucea; V Mladenov; E Pop; M Leba; N Mastorakis. AG LOANNOU THEOLOGOU 17-23, 15773 ZOGRAPHOU, ATHENS, GREECE: World Scientific and Engineering Acad and Soc, 2009. p. 178-183.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Complementary approaches for the computation of the independent number of a graph

AU - Brás, Maria do Carmo Proença Caseiro

N1 - 14th WSEAS International Conference on Applied Mathematics, Puerto de la Cruz, SPAIN, DEC 14-16, 2009

PY - 2009/1/1

Y1 - 2009/1/1

N2 - The problem of finding the independent number of an undirected graph is formulated as two equivalent Mathematical Programs with Linear Complementarity Constraints (MPLCC). A multistarting Lemke's method is introduced for dealing with the first formulation and is able to find a good approximate of the independent number in a finite number of iterations. A sequential complementary algorithm is also discussed for the second formulation and can find the independent number at least in theory. Some computational experience is included to highlight the efficacy of the complementary approaches for computing the independent number of graphs from the Dimacs collection.

AB - The problem of finding the independent number of an undirected graph is formulated as two equivalent Mathematical Programs with Linear Complementarity Constraints (MPLCC). A multistarting Lemke's method is introduced for dealing with the first formulation and is able to find a good approximate of the independent number in a finite number of iterations. A sequential complementary algorithm is also discussed for the second formulation and can find the independent number at least in theory. Some computational experience is included to highlight the efficacy of the complementary approaches for computing the independent number of graphs from the Dimacs collection.

KW - Linear Complementarity Problems

KW - Graph Theory

KW - Global Optimization

KW - Nonlinear Programming

M3 - Conference contribution

SN - 978-960-474-138-0

SP - 178

EP - 183

BT - Mathematics and Computers in Science and Engineering

A2 - Bulucea, C

A2 - Mladenov, V

A2 - Pop, E

A2 - Leba, M

A2 - Mastorakis, N

PB - World Scientific and Engineering Acad and Soc

CY - AG LOANNOU THEOLOGOU 17-23, 15773 ZOGRAPHOU, ATHENS, GREECE

T2 - 14th WSEAS International Conference on Applied Mathematics (MATH '09)

Y2 - 14 September 2009 through 16 September 2009

ER -