|
A
Natureza Combinatória de Muitos Problemas
Práticos,
Domingos Moreira Cardoso
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal
1as Jornadas de
Física e Matemática, Coimbra, 14 de Janeiro, 2009.
Muitos problemas práticos
são
usualmente modelados como problemas combinatórios cuja
resolução requer a
utilização de
técnicas de Matemática Discreta. Estão
neste caso
os problemas de
routing, sequenciamento de tarefas,
determinação de horários,
posicionamento de antenas em
sistemas wireless,
atribuição de frequências a
estações
emissoras, entre muitos outros.
Nesta apresentação, abordam-se alguns destes
problemas
segundo o ponto de vista dos respectivos modelos
matemáticos e descrevem-se técnicas para a sua
resolução. Relacionam-se as
partições de
conjuntos
parcialmente ordenados num número mínimo de
cadeias com
emparelhamentos máximos de grafos (especialmente
construídos para se obter esta
relação), tendo em
vista a resolução de certos problemas de
sequenciamento
de tarefas. Determinam-se extensões cromáticas em
grafos
com parte dos vértices coloridos, tendo em vista
a resolução de problemas de
atribuição de
frequências a estações emissoras ou com
o objectivo
lúdico de
completar puzzles Sudoku (entretenimento muito popular entre os
leitores de jornais e revistas). Finalmente,
estende-se esta última abordagem aos polinómios
cromáticos e aos polinómios de
extensões
cromáticas e suas
aplicações
|
Majorantes espectrais para o
número
de estabilidade de grafos.
Domingos Moreira Cardoso e Sofia Jorge Pinheiro
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal
Optimization 2007, Porto, July
22-25, 2007.
O majorante de Hoffman para o
número de estabilidade de grafos regulares é
estendido à cardinalidade de subconjuntos de
vértices que induzem grafos k-regulares em
grafos arbitrários (regulares ou não regulares) e
deduzem-se alguns majorantes espectrais
relacionados com este tipo de problemas.
|
Graph eigenvalue techniques for the
maximum cardinality k-regular induced subgraph problem.
Domingos Moreira Cardoso and Sofia Jorge Pinheiro
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal
Optimization 2007,
Porto, July
22-25, 2007.
A maximum independent
set, a
maximum induced matching and a maximum clique is a maximum cardinality
$0$-regular, $1$-regular and $(\omega(G)-1)$-regular (were $\omega(G)$
denotes the clique number of the graph $G$) induced subgraph,
respectively. An Hamiltonian cycle of a graph $G$ is a maximum
cardinality $2$-regular induced connected subgraph of the line graph
$L(G)$. According to (Cardoso, Kamínski and Lozin, 2007),
finding a maximum cardinality $k$-regular induced subgraph is an
NP-hard problem for any value of $k$. Using spectral graph theory
techniques, a few upper bounds on the size of $k$-regular induced
subgraph are introduced and some applications to particular cases
(maximum independent set problem, maximum clique problem and
Hamiltonian cycle existence problem) are analyzed. Finally,
computational experiments, comparing this spectral upper bounds with
some of the well known ones are presented.
|
Extensions of the Hoffman bound on
the stability number of regular graphs.
Domingos Moreira Cardoso
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal
6th Slovenian
International Conference on Graph Theory, Bled, Slovenia, 24-30 June,
2007.
The Hoffman upper
bound
on the stability number of regular graphs is extended to the size of
k-regular induced subgraphs of arbitrary graphs (regular or non
regular). For instance, an independent set and an induced matching are
0-regular and 1-regular induced subgraphs respectively. Some related
spectral upper bounds on the size of k-regular induced subgraphs are
deduced. Applications to extremal problems in graphs and computational
experiments are presented.
|
Convex quadratic programming
techniques on graphs and related spectral results.
Domingos Moreira Cardoso
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal
Seminar on
Applied
and Industrial Mathematics of the Mathematical Institute of Serbian
Academy of Sciences and Arts, Belgrade, June 5, 2007.
Convex
quadratic
programming upper bounds on the size of k-regular induced subgraphs are
introduced and a necessary and sufficient condition for this upper
bound be tight is presented. Some applications on extremal graph theory
are explored. Related spectral upper bounds are deduced and an
extension of the Hoffman bound for the stability number of regular
graphs is obtained.
|
Spectral results on graphs with regularity
constraints.
Domingos Moreira Cardoso and Paula Rama
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal
Aveiro
Workshop on Graph Spectra, Aveiro, Portugal, April 10-12, 2006.
Graphs
with
$(k,\tau)$-regular sets and equitable partitions are examples of graphs
with regularity constraints. A $(k,\tau)$-regular set of a graph G is a
subset of vertices $S \subseteq V(G)$ inducing a k-regular subgraph and
such that each vertex not in S has $\tau$ neighbors in S. The existence
of such structures in a graph provides some information about the
eigenvalues and eigenvectors of its adjacency matrix. For example, if a
graph G has a $(k_1,\tau_1)$-regular set $S_1$ and a
$(k_2,\tau_2)$-regular set $S_2$ such that $k_1-\tau_1=k_2-\tau_2$,
then $k_1-\tau_1$ is an adjacency eigenvalue of G. Additionally,
considering primitive strongly regular graphs, a necessary and
sufficient condition for a particular subset of vertices to be
$(k,\tau)$-regular is introduced. Another example comes from the
existence of an equitable partition in a graph. If a graph G, has an
equitable partition $\pi$ then its line graph, L(G), also has an
equitable partition, $\bar\pi$, induced by $\pi$, and the adjacency
matrix of the quotient graph $L(G)/\bar\pi$ is obtained from the
adjacency matrix of $G/\pi$.
|
Convex quadratic programmin techniques
on graphs.
Domingos Moreira Cardoso
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal
EURO
XXI, Reykjavik, Iceland, July 2-5, 2006.
Stable
sets, induced matchings and cliques are examples of regular induced
subgraphs in a graph. Convex quadratic programming techniques applied
to the determination of polynomial-time upper bounds on the size of
k-regular induced subgraphs are introduced. A necessary and sufficient
condition for a convex quadratic programming upper bound be tight is
proved. The recognition of graphs containing a vertex subset inducing
k-regular subgraphs with cardinality equal to the upper bound is
analyzed for particular values of k. Finally, some applications and
open problemas are presented.
|
|
A matemática e os seus
problemas.
Domingos Moreira Cardoso
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal
Semana
da Ciência e Tecnologia, Universidade de Aveiro, 21-27 de
Novembro, 2005.
O
título desta apresentação tem um
triplo sentido. Na verdade, com ela, pretende-se abordar não
só as dificuldades intrínsecas ao estudo da
matemática, como também a
utilização dos problemas matemáticos
enquanto instrumentos de ensino/aprendizagem e ainda, ao seu mais alto
nível, destacar os contributos que muitos problemas e
conjecturas deram para o seu extraordinário desenvolvimento.
|
|
On the maximum cardinality of k-regular
induced subgraphs.
Domingos Moreira Cardoso
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal
INFORMS
- Annual Meeting, San Francisco, USA, 13-16 November, 2005.
A
maximum stable set, maximum induced matching and a maximum clique is a
maximum cardinality 0-regular, 1-regular and $(\omega(G)-1)$-regular
induced subgraph, respectively. An Hamiltonian cycle of G is a maximum
cardinality 2-regular induced connected subgraph of the line graph
L(G). Since the determination of the maximum cardinality of a k-regular
induced subgraph is NP-hard, it is crucial to
obtain polynomial-time upper and lower bounds. In this report, a
polynomial time upper bound on the maximum cardinality of a k-regular
induced subgraph is proposed, a necessary and sufficient condition for
this bound be tight is introduced and some applications are presented.
|
|
A Spanning Star Forest Model for the
Diversity Problem in Automobile Industry.
Agostinho Agra1, Domingos M. Cardoso1,
Orestes Cerdeira2 and Eugénio Rocha1
1Universidade
de Aveiro, Departamento de Matemática, 3810-193 Aveiro,
Portugal
2Universidade
Técnica de Lisboa, Instituto Superior de Agronomia, Tapada
da Ajuda, 1349-017, Lisboa, Portugal
ECCO
XVIII, Minsk, Belarus, May 26-28, 2005.
Cars
are purchased with a set of active options (airbags, air conditioned,
radio car, etc.) which varies from one client to another. A car has an
active option connection if it is prepared to include such option as an
active one (that is, the car has all the necessary material for the
connection). In general, each unit is produced with more active option
connections than the ones which became active. If the car has an active
option connection which not became active, then there is a cost (for
instance in copper and several other material related with the
connections). The global cost of option connections is very high in
automobile industry and thus it is crucial to produce cars prepared
with a set of active option connections close as possible to the set of
active options purchased by each client. Furthermore, for technical
reasons, it is not possible to produce a large variety of different
option connection configurations. The main problem is to design an
algorithmic strategy to minimize the diversity of option connection
configurations from an universe determined according to the statistic
data about costumer preferences and selling expectations and also to
minimize the supply cost of produced configurations, fulfilling the
market requirements. This problem is formalized as the minimum arc cost
sum spanning star forest of the inclusion relation configuration
digraph, with no more than k stars. There are
several versions of the star forest problem. We deal with an inclusion
relation configuration digraph DG with arc costs
and with its spanning star forests, each one of which is a spanning
subdigraph defined by a forest of star trees (a star tree is a complete
bipartite graph K1,p, which
is a tree with one central vertex of degree p and p
end-vertices with degree 1). In our model all the
arcs of each star are directed from the center to the end-vertices and
we may wish to find a spanning star forest of DG
which is minimal with respect to the sum of the arc costs and bounded
with respect to the number of stars. The complexity of the problem is
proved, an algorithmic technique is proposed and a numerical example is
presented.
|
|
Eigenvectors and
eigenvalues of graphs with regularity constraints.
Domingos M. Cardoso1, Charles Delorme2
and Paula Rama1
1Universidade
de Aveiro, Departamento de Matemática, 3810-193 Aveiro,
Portugal
2 Lab.
de
Recherche en Informatique, Univ. Paris-Sud, 91405 Orsay, France
Conference
on Graph Theory in memory of Claude Berge, Paris, France, July 5-9,
2004.
Graphs
with (k,t)-regular sets
are examples of graphs with regularity constraints. A (k,t)-regular set of a graph G is a
subset of vertices S inducing a k-regular subgraph and such
that each vertex not in S has t
neighbors in S. The (k,t)-regular
sets can model several problems. For example, if a simple graph (i.e, a
graph with no loops nor parallel edges) has a Hamiltonian cycle then
its line graph has a (2,4)-regular set or, equivalently, if a simple
graph is Hamiltonian then the line graph of its subdivision (that is,
the graph obtained after the insertion of a vertex in each edge has a
(2,2)-regular set. Another example comes from the conclusion that a
simple graph has a perfect matching if and only if its line graph has a
(0,2)-regular set, also G has a perfect (which is an induced matching
covering all the edges) if and only if its line graph L(G) has a
(0,1)-regular set. The spectral properties of the adjacency and
Laplacian matrices of these graphs can help to recognize these sets. In
this paper, basic properties of regular graphs with (k,t)-regular sets
are presented. Namely we conclude that if the 4th Moore graph exists
and has a maximum independent set with 400 vertices then it has no (k,t)-regular sets with k-t=7. Additionaly, if G is a
primitive strongly regular graph with parameters (n,p;a,c) and
adjacency matrix A with eigenvalue l
not in {p, k-t}, then S
is a (k,t)-regular set if
and only if every eingenvector correspounding to l
is orthogonal to the characteristic vector of S.
|
|
Continuous optimization techniques
on graphs.
Domingos M. Cardoso
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal
Workshop
on Challenges of Continuous Optimization in Theory and Applications,
Rhodes, Greece, July 2-3, 2004.
The
study of effective computable upper bounds for the stability number of
graphs lead to the determination of a convex quadratic programming
upper bound for the stability number and also to the study of graphs
for which this upper bound is attained. Such graphes are called graphs
with convex-QP stability number. On the other hand, the
recognition of these graphs, in particular, the characterization of
families of graphs for which such recognition can be done in
polynomial-time is related with the existence of (k,t)-regular sets, with k=0 and t = -lmin(AG),
where lmin(AG)
denotes the minimum eigenvalue of the adjacency matrix AG.
A (k,t)-regular set of a
graph G is a subset of vertices S inducing a k-regular subgraph and
such that each vertex not in S has t neighbors in S. Therefore, every
p-regular graph as a (p,0)-regular set. It is known that a graph G has
convex-QP stability number if and only if it has an
independent set S such that every vertex out of S has not less than -lmin(AG)
neighbors in S. Furthermore, it is also known that a p-regular graph G
has convex-QP stability number if and only if it has
a (0,t)-regular set, with
t
= -lmin(AG).
On the other hand, a connected graph which is not a star neither a
triangle has a perfect matching if and only if its line graph has
convex-QP stability number. In this paper the
combinatorial characterization of graphs for which we have no a
polynomial-time algorithm to if it has (or not) convex-QP
stability number is introduced and some families of graphs for which
such polynomial-time algorithm can be obtaine are presented.
|
|
Moore graphs and (k,t)-regular sets..
Domingos M. Cardoso
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal
Seminar
on Applied Mathematics, Institute of Mathematics, Poznan University of
Technology, January 7, 2004, Poznan, Poland.
Abstract
- Several nice properties of the strongly regular graphs belonging to
the Moore family are presented. Namely, the ones related with the
existence of (k,t)-regular
sets. Some graph spectral implications are also analysed and the open
problem of the existence of the fourth graph of Moore is referred.
Keywords -
graph
theory, strongly regular graphs.
|
|
Abordagens analíticas
de um problema combinatório de
descodificação de imagens.
Domingos M. Cardoso e M. Helena Silva
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal
Congreso
Galego de Estatística e Investigación de
Operacións, Vigo, Novembro 5-7, 2003.
Resumo
- Apresenta-se um modelo de codificação de
imagens, bem como duas formulações para o
problema da respectiva descodificação. A primeira
formulação é baseada em
programação inteira e a segunda é
baseada na determinação de um estável
máximo de um certo grafo associado. Em todos os casos, se
recorre a métodos analíticos para a
resolução do problema. No caso da
formulação no contexto da teoria dos grafos,
recorre-se à programação semidefinida
e à programação quadrática
convexa combinadas com branch-and bound. Fizeram-se as respectivas
implememntações e compararam-se os diferentes
resultados obtidos. Finalmente, analisaram-se alguns casos em que a
codificação não determina univocamente
as respectivas imagens.
Keywords -
mathematical
modeling, graph theory, integer programming.
|
|
Uma abordagem algébrica de
grafos fortemente regulares
Domingos M. Cardoso
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal
(dcardoso@mat.ua.pt)
Homenagem
ao Professor Mário da Silva Rosa, Coimbra, October 15, 2003.
Resumo
- Os grafos fortemente regulares, são grafos regulares,
não nulos nem completos nos quais, dados dois
vértices x e y, o número de vértices
adjacentes a ambos depende apenas de x e y serem ou não
adjacentes. O ciclo com 5 vértices e o grafo de Petersen
constituem os grafos fortemente regulares de menor ordem, com algum
interesse. Nesta apresentação, faz-se um resumo
dos principais resultados de natureza algébrica que
caracterizam os grafos fortemente regulares, introduzem-se outros que
garantem a existência de certas subestruturas
combinatórias com restrições de
regularidade e descrevem-se alguns problemas em aberto.
Keywords -
graph
theory.
|
|
On Laplacian eigenvectors and
eigenvalues and almost equitable partitions
Domingos M. Cardoso,1 Charles Delorme2
and Paula C. Rama1
1Universidade
de Aveiro, Departamento de Matemática, 3810-193 Aveiro,
Portugal
2 Lab.
de
Recherche en Informatique, Univ. Paris-Sud, 91405 Orsay, France
Combinatorics
in Oporto, Porto, September 12-17, 2003.
Abstract
- Some relations between Laplacian eigenvectors and eigenvalues and the
existence of almost equitable partitions (which are generalizations of
equitable partitions) are introduced. It is proved that there exists
graphs without any nontrivial almost equitable partition even when they
have non null integer Laplacian eigenvalues .
Keywords -
graph
theory, spectra of graphs.
|
|
On a subclass of
well-covered graphs
Rommel Barbosa1 and Domingos M. Cardoso2
2Universidade
Federal de Mato Grosso, Departamento de Matemática,
78060-900, Cuiabá-MT, Brasil (rommel@acm.org)
2Universidade
de Aveiro, Departamento de Matemática, 3810-193 Aveiro,
Portugal (dcardoso@mat.ua.pt)
Thirty-fourth
Southest International Conference on Combinatorics, Graph Theory, and
Computing, Boca Raton, Florida, March 3-7, 2003. October 27-31, 2002.
Abstract
- A graph G is well-covered if
all maximal independent sets of vertices in G have
the same cardinality. A well-covered graph G is p-regular-stable
if for all maximal independent sets of vertices I
in V(G), the cardinality of the intersection of NG(v)
with I is constant, for any vertex v
not in I. Here we show some ways to build graphs
with this property.
Keywords -
well-covered
graphs, regular-stable graphs.
|
|
Grafos Fortemente Regulares
Domingos M. Cardoso
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal
(dcardoso@mat.ua.pt)
Seminar
on Combinatorics of Pure Mathematics Department of Porto University,
Porto, December 3, 2002.
Resumo
- Os grafos fortemente regulares são grafos regulares
não nulos nem completos onde o número de vizinhos
comuns a dois vértices x e y depende apenas de x e y serem
ou não adjacentes. Nesta apresentação
abordam-se as principais propriedades algébricas (em
particular as espectrais) dos grafos fortemente regulares,
introduzem-se desigualdades poliédricas que os caracterizam
e analisam-se alguns problemas em aberto relacionados com este tipo de
grafos.
Keywords -
graph
theory.
|
|
Confirmation Results on
Multiattribute Ranking Problems
Domingos M. Cardoso1 and Jorge Freire de Sousa2
1Universidade
de Aveiro, Departamento de Matemática, 3810-193 Aveiro,
Portugal (dcardoso@mat.ua.pt)
2Universidade
do Porto, Faculdade de Engenharia, 42000-465 Porto, Portugal
(jfsousa@fe.up.pt)
XI
Latin-Iberian American Congress of Operations Research - CLAIO,
Concepcion, October 27-31, 2002.
Abstract
- Ranking problems arise from the knowledge of several binary relations
defined on the same set of objects, which we intend to rank. However,
in this process, some inconsistencies can arise. Herein, a confirmation
technique for ranking solutions of multiattribute problems is proposed
by confirming them as linear extensions of a weighted sum of preference
relations. A technique to recognize critical preference pairs of
alternatives and a threshold level for the confirmation of ranking
solutions obtained by arbitrary methodologies are presented. A partial
order on the set of different solutions obtained by arbitrary
methodologies applied to the same multiattribute ranking problem is
also introduced. Finally, a numerical example and a case study
highlight the application of the proposed techniques.
Keywords -
multicriteria
decisionm making: multiattribute ranking problems; graphs.
|
|
A partial order on the set
of solutions of a multiattribute ranking problem
Domingos M. Cardoso1 and Jorge Freire de Sousa2
1Universidade
de Aveiro, Departamento de Matemática, 3810-193 Aveiro,
Portugal (dcardoso@mat.ua.pt)
2Universidade
do Porto, Faculdade de Engenharia, 42000-465 Porto, Portugal
(jfsousa@fe.up.pt)
56th
Meeting of the European Working Group MCDA, Coimbra, Portugal, October
3-5, 2002.
Abstract
- Confirmation techniques of linear order solutions are becoming
fundamental tools for multiattribute ranking problems. Namely, when one
ranking solution must be chosen among several ones obtained by
different methodologies applied to the same multiattribute problem. In
this presentation, a contribution for the implementation of these
confirmation techniques is given, based on an overall weighted sum
relation obtained for each multiattribute ranking problem. Such overall
weighted sum relation (which is a quasi-order relation) automatically
produces the preference levels needed to the rank solution to become
one of their linear extensions. The methodology allows the recognition
of critical preference pairs of alternatives (from the point of view of
some criteria) for which the preference level must be the lowest.
Furthermore, a threshold for the confirmation failure of a linear order
solution is introduced and this threshold is applied to define a
partial order on the set of ranking solutions obtained by different
methodologies. The application of the above results is highlighted by a
numerical example and also by a case study where the proposed
techniques were tested.
Keywords -
confirmation
of multiattribute ranking solutions, posets, linear extensions.
|
|
Polynomial-time recognition of
graphs with convex-QP stability number in particular hereditary graph
classes
Domingos M. Cardoso
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal (dcardoso@mat.ua.pt)
Fourth
Cracow Conference on Graph Theory, Czorsztyn, September 16-20, 2002.
Abstract
- The focus of this presentation is the study of simple
graphs G of order n and at
least one edge for which uG
(-lmin(AG))
= a(G),
with lmin(AG)
denoting the minimum eigenvalue of the adjacency matrix AG
and uG(t) denoting the optimal value of
the quadratic programming problem (PG(t)):
uG(t) = max {2êTx-xT((1/t)AG+In)x,
x >= 0},
(where
ê is the all ones vector of Rn,
t
is a scalar greater than zero and In
is the identity matrix of order n) which is convex
for t greater or equal
to -lmin(AG).
These graphs are known as graphs with convex-QP
stability number. Given an arbitrary graph G, since
the components of the optimal solutions of (PG(t)) are between 0 and 1, it is
immediate that uG(t) =
a(G) if and only if (PG(t)) has an integer optimal
solution. However, to recognize if such solution exists, among the
optimal ones, is an NP-hard
problem, even for convex quadratic programming problems. Carlos Luz in
1995 introduced the following necessary and sufficient
condition: a graph G, with at least one edge, has convex-QP
stability number if and only if for a maximum independent set of
vertices S of G (and then for all) -lmin(AG)
is less or equal |NG(v) \cap S| for
all v \in S, where NG(v) denotes the
set of neighbors of the vertex v. There is an infinite number
of graphs with convex-QP stability number. For
instance, a connected graph with at least one edge, which is not a star
neither a triangle, has a perfect matching if and only if its line
graph has convex-QP stability number. On the other
hand, if G is a connected graph such that |E(G)|
is even then L(L(G)) has convex-QP
stability number. Despite remaining, as an open problem, to find a
polynomial-time algorithm for the recognition of graphs with convex-QP
stability number, we introduce some results which allows the
polynomial-time recognition of graphs with convex-QP
stability number, when they belong to several particular hereditary
graph classes.
Keywords -
graph
theory, independent sets, programming involving graphs.
|
|
Spectral results on graphs
with equitable bipartitions
Domingos M. Cardoso1 and Paula C. Rama2
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal
(1dcardoso@mat.ua.pt, 2prama@mat.ua.pt)
Fourth
Cracow Conference on Graph Theory, Czorsztyn, September 16-20, 2002.
Abstract
- A set of vertices S of a graph G
is (k,t)-regular
if induces a k-regular subgraph of G,
such that every vertex not in S has t neighbours in S.
A bipartition of the vertex set of a graph G (V1,V2)
is equitable if V1 is (k1,t1)-regular
and V2 is (k2,t2)-regular.
If a graph is p-regular then every (k,t)-regular set
S defines
an
equitable bipartition (S,V(G)\S). It is known that a connected graph
which is not a star neither a triangle has a perfect matching iff its
line graph L(G) has a (0,2)-regular set. In this
presentation some spectral results on graphs with (k,t)-regular
sets are introduced, in particular, the minimum eigenvalue of the
adjacency matrix of some graphs with equitable bipartitions is deduced
and relations between its combinatorial structure and the corresponding
eigenspace is presented. Special attention is given to (0,t)-regular and
(1,t)-regular
sets which are maximal stable sets and maximum induced matchings,
respectively.
Keywords -
graph
theory, spectra of graphs.
|
|
On graphs with stability number
equal to the optimal value of a convex quadratic program
Domingos M. Cardoso
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal (dcardoso@mat.ua.pt)
Workshop
Latino-Americano de Cliques em Grafos, Rio de Janeiro, April 17-19, 2002.
Abstract
- Since the Motzkin-Straus result on the clique number of graphs,
published in 1965, where they show that the size of the largest clique
in a graph can be obtained by solving a quadratic programming problem,
several results on the continuos approach to the determination of the
clique number of a graph or, equivalently, to the determination of the
stability number of its complement, have been published. Such approach,
in general, is based on an indefinite quadratic programming problem
formulation which is NP-hard. In this presentation, several properties
of the optimal values of a parametric family of quadratic programs,
which are convex for particular values of the parameter, are presented,
as well as the determination of upper and lower bounds on the stability
number of graphs by solving these convex quadratic programs. The
recognition of graphs for which the stability number is equal to the
optimal value of a convex quadratic program is analysed. Furthermore,
for particular hereditary graph classes, a polynomial-time recognition
of graphs with stability number equal to the optimal value of a convex
quadratic programming problem is introduced.
Keywords -
graph
theory, stability number, quadratic programming.
|
|
Uma abordagem
combinatória de um problema de
descodificação de imagens
Domingos M. Cardoso1 e M. Helena Silva2
1Universidade
de Aveiro, Departamento de Matemática, 3810-193 Aveiro,
Portugal (dcardoso@mat.ua.pt)
2Instituto
de Telecomunicações da Universidade de Aveiro,
3810-193 Aveiro, Portugal (lena@mat.ua.pt)
io2002,
Guimarãe, Março 24-27, 2002.
Resumo
- Em certos problemas de codificação de imagens
as matrizes de pixels são representadas por
sequências de números associados às
suas linhas e colunas. Nesta apresentação
propõe-se um modelo combinatório, baseado na
determinação do estável
máximo de um grafo associado às referidas
sequências numéricas, com vista à
respectiva descodificação, e faz-se um estudo
comparativo entre algumas abordagens adoptadas para a
obtenção de uma solução
aproximada deste problema que, como se sabe, em geral, é NP-difícil.
Keywords -
graph
theory, combinatorial models, NP-hard problems.
|
|
Resultados espectrais em
grafos regulares estáveis
Domingos M. Cardoso1 e Paula C. Rama2
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal
(1dcardoso@mat.ua.pt, 2prama@mat.ua.pt)
io2002,
Guimarãe, Março 24-27, 2002.
Resumo
- O menor valor próprio da matriz de adjacência de
grafos cujo número de estabilidade pode ser determinado por
programação quadrática convexa,
apresenta propriedades combinatórias muito particulares.
Dentro desta classe de grafos analisamos o caso dos grafos regulares
que necessariamente são regulares estáveis (i.e,
são grafos que admitem um estável
máximo, S, em que os vértices não
pertencentes a S têm um número de vizinhos
constante em S). Este estudo inclui a utilização
de partições equilibradas e de
técnicas de "switching" em grafos regulares, com vista
à obtenção de
relações entre propriedades espectrais e
combinatórias.
Keywords -
graph
theory, spectra of graphs.
|
|
Produtos
lexicográficos e cartesianos de grafos: algumas propriedades
Rommel M. Barbosa1 e Domingos M. Cardoso2
1Uniniversidade
Federal de Mato Grosso, ICET, Departamento de Matemática,
78060-900 Cuiabá-NT, Brasil (rmbarbosa@yahoo.com)
2Universidade
de Aveiro, Departamento de Matemática, 3810-193 Aveiro,
Portugal (dcardoso@mat.ua.pt)
io2002,
Guimarãe, Março 24-27, 2002.
Resumo
- Dados dois grafos simples (i.e. sem arestas em paralelo, nem lacetes)
G e H,
designa-se por produto cartesiano entre G e H,
o grafo GxH cujo conjunto de vértices
vem dado por V(GxH)=V(G)xV(H) e o conjunto de
arestas E(GxH)={[(u,x),(v,y)] : u=v e
xy pertence a E(H), ou uv pertence a
E(G) e x=y}. Por sua vez, designa-se por
produto lexicográfico de G e H,
o grafo G*H cujo conjunto de vértices
é V(G*H)=V(G)xV(H) e o conjunto de
arestas é E(G*H)={[(u,x),(v,y)] :
uv pertence a E(G) ou u=v
e xy pertence a E(H)}. Nesta
apresentação analisam-se algumas propriedades
combinatórias destes produtos de grafos e, a partir deles,
introduzem-se algumas técnicas de
construção de grafos com propriedades
combinatórias pré-definidas.
Keywords -
graph
theory, combinatorics.
|
|
Problemas combinatórios
em conjuntos parcialmente ordenados
Domingos M. Cardoso
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal (dcardoso@mat.ua.pt)
Encontro
Nacional da SPM, Coimbra, Fevereiro 5-8, 2002.
Resumo
- As relações de ordem parcial e as suas
representações algébricas e
combinatórias, proporcionam estruturas
matemáticas poderosas para a
modelaçãoo e resolução de
muitos problemas de natureza combinatória. Nesta
apresentaçãoo, analisam-se os principais
parâmetros associados a um conjunto parcialmente ordenado
(como sejam, o comprimento, a largura e a dimensão), bem
como as suas principais subrelações e
extensões, com particular destaque para as
relações de ordem intervalar, as semitransitivas,
as semiordens, as relações
de ordem fraca e as lineares. Estudam-se
as respectivas representações
combinatórias (por intermédio de grafos) e
algébricas (com recurso aos espaços vectoriais
associados) e abordam-se algumas técnicas para a
determinação de extensões fracas e
lineares. Finalmente referem-se alguns problemas de
investigação corrente relacionados com conjuntos
parcialmente ordenados e suas aplicações.
Keywords -
posets,
graph theory, combinatorics.
|
|
Stable sets, matchings and related
results
Domingos M. Cardoso
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal
(cardoso@mat.ua.pt)
Optimization
2001, Aveiro, July 23-25, 2001.
Abstract
- It is well known that despite the problem of determining a maximum
stable set of a graph being NP-hard there are very efficient
polynomial-time algorithms for solving this problem for some particular
classes of graphs. In this presentation we consider several techniques
for determining maximum stable sets by convex quadratic programming for
some types of graphs (which we call graphs with convex quadratic
stability number), as well as its characterization. Additionally,
extending the obtained results for the characterization of graphs with
convex quadratic stability number, we characterize the graphs with
perfect matching and the maximum matching is determined by convex
quadratic programming applied to line graphs.
Keywords -
graph
theory, maximum stable sets, maximum matchings.
|
|
Extensions of the Motzkin-Straus
Result on the Stability Number of Graphs
Domingos M. Cardoso
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal
(cardoso@mat.ua.pt)
Max-Clique'01,
Klagenfurt, May 31 - June 3, 2001.
Abstract
- The result, published in 1965 by Motzkin and Straus, where the
stability number of a graph is determined minimising an indefinite
quadratic form on the simplex, is now extended to a family of quadratic
programming problems that are convex for several types of graphs. From
the obtained results, easily computed lower and upper bounds for the
stability number of arbitrary graphs are proposed.
Keywords -
graph
theory, stable sets, programming involving graphs.
|
|
A Matemática e o
Desenvolvimento Tecnológico
Domingos M. Cardoso
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal (dcardoso@mat.ua.pt)
Semana
da Ciência e Tecnologia da Universidade de Aveiro, Aveiro, 21
de Novembro de 2000.
Resumo
- Embora a maior parte do desenvolvimento científico e
tecnológico, se tenha dado, essencialmente, nos
últimos 50 anos, tal desenvolvimento seria
impossível sem a utilização das
teorias matemáticas produzidas ao longo de dois mil anos,
com especial destaque para os avanços mais significativos
conseguidos a partir do século XVII. Desde o estudo
aerodinâmico dos aviões até aos voos
espaciais de grande precisão, passando pela
circulação intercontinental, a alta velocidade,
de grandes volumes de dados, devidamente codificados e compactados,
tudo assenta em teorias matemáticas previamente
desenvolvidas e/ou de investigação corrente, como
sejam, o cálculo diferencial, a combinatória,
etc. Esta palestra incide sobre o papel e importância da
Matemática na inovação
científica e tecnológica necessária
à resolução dos nossos problemas
quotidianos.
Keywords -
mathematics
education, history and biography.
|
|
Aplicações da
Matemática Discreta
Domingos M. Cardoso
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal (dcardoso@mat.ua.pt)
Conferências
da SPM para celebrar o Ano Mundial da Matemática
Escola Secundária Clara de Resende, Porto, 10 de Maio de
2000.
Resumo
- A Matemática Discreta engloba diferentes
especializações, como sejam, a Teoria dos Grafos,
a Combinatória (onde podemos incluir a
Optimização Combinatória) a Teoria dos
Números, etc. A sua intensa
investigação, principalmente a apartir do
século XVIII, tem autonomizado estas diferentes
especializações, transformando-as em grandes
áreas de estudo com resultados relevantes para o
desenvolvimento científco e tecnológico dos
nossos dias. Nesta apresentação procura-se
responder a algumas questões básicas relacionadas
com a origem da Teoria dos Grafos, o seu desenvolvimento, as suas
aplicações, os problemas combinatórios
que lhe estão associados e algumas ferramentas
matemáticas (simples) relevantes para a sua
resolução, bem como referir algumas
implicações nos avanços
tecnológicos.
Keywords -
mathematics
education, history and biography.
|
|
Validation in Alternative
Selection Problems - Part I: Tools from Combinatorics and Graph Theory
Domingos M. Cardoso1 and Jorge Freire de Sousa2
1Universidade
de Aveiro, Departamento de Matemática, 3810-193 Aveiro,
Portugal (dcardoso@mat.ua.pt)
2Universidade
do Porto, Faculdade de Engenharia, 42000-465 Porto, Portugal
(jfsousa@fe.up.pt)
4th
International Conference on Operations Research, Habana, March 6-10,
2000.
Abstract
- Many decision problems consist in selecting an alternative from
several ones that are evaluated under conflicting attributes. A large
variety of approaches has been developed in order to help the decision
makers in the choice of the best alternative with maximum objectivity.
The most popular of these kind of approaches are the
pairwise-comparison method in the analytic hierarchy process
and the ones based on the expected utility theory.
Despite the fact that many approaches of multicriteria decision
analysis do not assume any strong condition of consistency, as it is
the case of transitivity in the performed relative preferences, in
general, the main goal is to get an explicitly or implicitly linear
order for the set of alternatives. In this presentation several tools
from combinatorics and graph theory are proposed for validation of
alternative selection decision techniques.
Keywords -
multicriteria
analysis, combinatorics, graph theory .
|
|
Validation in Alternative
Selection Problems - Part II: Analysis of an Application in the
Acquisition of Urban Buses
Domingos M. Cardoso1 and Jorge Freire de Sousa2
1Universidade
de Aveiro, Departamento de Matemática, 3810-193 Aveiro,
Portugal (dcardoso@mat.ua.pt)
2Universidade
do Porto, Faculdade de Engenharia, 42000-465 Porto, Portugal
(jfsousa@fe.up.pt)
4th
International Conference on Operations Research, Habana, March 6-10,
2000.
Abstract
- The process of selecting a supplier for a set of urban buses is a
multiattribute decision problem of great complexity. Several criteria
reflecting technical, commercial and economical characteristics, price
and payment conditions, guarantee agreements supplement, provision of
spare parts, level of service of the supplier, between others, must be
considered. In the judgements about the different options, the
performance criteria must be taken into account and there is the need
to apply techniques that produce a strictly hierarchy in order that the
final choice will be not based in a purely subjective weighting of the
alternatives. In this presentation a case study related with the
analysis of proposals to supply a set of urban buses for a
public transport fleet is presented. The results obtained from the
applied multicriteria decision methodology and from several validation
techniques which use tools from combinatorics and graph theory are
compared.
Keywords -
operations
research, multicriteria analysis.
|
|
On a parallel
implementation of the generalized simplex method
João N. Clímaco1,
João P. Costa2 and Domingos M. Cardoso3
1University
of Coimbra, Faculty of Economics, 3004-512 Coimbra, Portugal
(jclimaco@inescc.pt)
2University
of Coimbra, Faculty of Economics, 3004-512 Coimbra, Portugal
(jpaulo@sonata.fe.uc.pt)
3Universidade
de Aveiro, Departamento de Matemática, 3810-193 Aveiro,
Portugal (dcardoso@mat.ua.pt)
15th
Triennial Conference of the International Federation of Operational
research Societies - IFORS'99, Beijing, August 16-20, 1999.
Abstract
- A generalized simplex method was presented in (Cardoso and Climaco,
1992). The basic idea underlying the method is that the movements
towards the optimum are made throught the relative interior of feasible
faces of arbitrary dimension rather than along edges (1-dimension
faces) as in the classical simplex method. In this work we discuss the
implementation of this approach in a parallel processing machine.
Computational tests and some conclusions are also presented.
Keywords -
hybrid
methods in real and integer programming, parallel algorithms..
|
|
Multicriteria Models of Storage
Assignment Problems
Domingos M. Cardoso
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal (dcardoso@mat.ua.pt)
15th
Triennial Conference of the International Federation of Operational
research Societies - IFORS'99, Beijing, August 16-20, 1999.
Abstract
- Storage assignment problems appear in automatic storage systems,
flexible manufacturing systems (systems with a large variety of
products), wide distribution centres, among others. In this
presentation a case-study, where there is storage area between the
production and delivery systems with high level of input and output
flow of products, is described. Multicriteria models as well as the
used multicriteria techniques are analysed and some computational
experiments are presented.
Keywords -
storage
assignemet problems, multicriteria combinatorial optimization,
real-world problems.
|
|
Resultados espectrais em grafos e
aplicações
Domingos M. Cardoso
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal (dcardoso@mat.ua.pt)
Seminário
do Grupo de Análise Numérica,
Optimização e Aplicações do
Departamento de Matemática da Universidade de Coimbra, 1999.
Resumo
- Dado um grafo
G (sem arestas múltiplas nem lacetes) entende-se
como espectro de G o conjunto dos valores
próprios da sua matriz de adjacência, AG.
Em certas publicações, porém, por
conveniência dos resultados de natureza
combinatória a obter, adoptam-se, em alternativa, os valores
próprios correspondentes à matriz laplaciana de G,
DG-AG,
onde DG identifica a
matriz diagonal cujos elementos principais correspondem aos respectivos
graus dos vértices. Para os distinguir denota-se, cada um
destes valores próprios, por li(AG)
e li(DG-AG),
respectivamente. Existem relações de
vária ordem, quer entre os valores próprios de
AG e os de DG-AG,
quer entre estes e certos parâmetros de natureza
combinatória associados aos grafos, como sejam, a sua
conexidade, o número de clique, o número de
estabilidade, etc. Nesta apresentação
relacionam-se os valores próprios de AG
com os de
DG-AG e
abordam-se os
resultados básicos que relacionam estes valores
próprios com os valores de alguns parâmetros.
Adicionalmente, introduzem-se vários resultados onde o menor
valor próprio de AG tem lugar de
destaque na determinação do número de
estabilidade de certos grafos, detecção de grafos
que admitem emparelhamentos perfeitos, etc.
Keywords -
graph
theory, spectra of graphs.
|
|
The Overflow
Traffic from the Erlang-B System - what convexity properties?
J. Sá Esteves1, José
Craveirinha2 and Domingos M. Cardoso1
1Universidade
de Aveiro, Departamento de Matemática, 3810-193 Aveiro,
Portugal
1Universidade
de Coimbra, Departamento de Matemática, 3810-193 Aveiro,
Portugal
Encontro
Nacional da SPM, Braga, Fevereiro 9-12, 1998.
Abstract
- This contribution focuses on the study of some analytical properties
of an high transcendental function well known by Teletraffic theorists,
designated as Erlang-B function, which gives the blocking probability
of an arriving call in the M/M/x loss system. This and other related
functions play an important role in many models of Teletraffic Theory
and has many applications in multiple Teletraffic engineering
problems. Denoting by a the offered traffic and x
the number of circuits, this work focus on the properties of the
overflow traffic function A(a,x) from an Erlang-B
system, when (a,x) is in R+xR.
Keywords -
teletraffic
theory, Erlang-B system, derivatives of overflow traffic, convexity
properties.
|
|
Temas e Problemas em
Combinatória
Domingos M. Cardoso
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal (dcardoso@mat.ua.pt)
Encontro
Nacional da SPM, Braga, Fevereiro 9-12, 1998.
Resumo
- Muitos dos problemas da teoria de grafos, pela sua natureza
combinatória, podem ser abordados, com vantagem, recorrendo
a resultados provenientes das teorias combinatórias, como
são o caso dos obtidos a partir do estudo das
relações de ordem parcial. Nesta
apresentação utilizam-se vários
resultados da teoria dos conjuntos parcialmente ordenados, como sejam
os teoremas de Erdos-Szekeres (1935), de Dilworth (1950) e o que
estabelece o resultado dual do teorema de Dilworth (publicado por
Mirsky em 1971), na resolução de
vários problemas associados a grafos, nomeadamente, na
determinação de majorantes e minorantes,
respectivamente, para o número cromático e para o
número de estabilidade de um grafo. A partir dos
conceitos de coloração de vértices e
de conjunto independente de vértices de um grafo,
introduzindo-se uma relação de ordem parcial
adequada, a desigualdade clássica entre o número
de vértices de um grafo, |V(G)|, e o produto do seu
número de estabilidade, a(G),
pelo seu número cromático, c(G),
ou seja, |V(G)| <= a(G)c(G), decorre de modo imediato
por aplicação do teorema de Dilworth. Com recurso
ao resultado dual do Teorema de Dilworth, prova-se que os grafos de
comparabilidade de relações de ordem parciais
são grafos perfeitos, ou seja,, são tais que para
qualquer dos seus subgrafos o respectivo número
cromático é igual ao correspondente
número de clique (cardinalidade do maior subgrafo completo)
e, sem recurso ao teorema do grafo perfeito de Lovász
(1972), utilizando unicamente o teorema de Dilworth, prova-se ainda que
os grafos de incomparabilidade de relações de
ordem parciais são também grafos perfeitos.
Keywords -
posets,
graph theory, combinatorics.
|
|
A quadratic programming approach
to the determination of an upper bound on the weighted stability number
Domingos M. Cardoso1 and Carlos J. Luz2
1Universidade
de Aveiro, Departamento de Matemática, 3810-193 Aveiro,
Portugal (dcardoso@mat.ua.pt)
2Instituto
Politécnico de Setúbal, Escola Superior de
Tecnologia, 2914-508 Setúbal, Portugal (cluz@mat.est.ips.pt)
Joimt
International Meeting EURO-INFORMS, Barcelona, July 14-17, 1997.
Abstract
- In a previous work the authors have introduced an upper on the
stability number of a graph and several of its properties were given.
The determination of this upper bound was done by a quadratic
programming approach whose implementation has given good computational
results. We now extend this bound to the weighted case, i.e., an upper
bound on the weighted stability number of an arbitrary graph with node
weights is presented. Similarly to the no weighted case, the deduced
bound allows us to give a heuristic for determining th maximum weight
stable set. Also a necessary and sufficient condition to a weighted
graph attains the given bound is proved.
Keywords -
graph
theory, stability number, programming involving graphs.
|
|
The well-known linear
programming approachs and a generalization of the simplex method - a
unified discussion
Domingos M. Cardoso1 and Carlos N.
Clímaco2
1Universidade
de Aveiro, Departamento de Matemática, 3810-193 Aveiro,
Portugal (dcardoso@mat.ua.pt)
2University
of Coimbra, Faculty of Economics, 3004-512 Coimbra, Portugal
(jclimaco@inescc.pt)
IFORS
93, Lisboa, July 12-16, 1993.
Abstract
- A new approach designated by generalized simplex method is discussed.
Comparisons with the classical simplex method and the interior point
methods are presented. It must be emphasized that the main feature of
the generalized simplex method is related to the use of hybrid
techniques, combining interior point methods with the classical simplex
method. These approaches are specially useful for large scale problems.
Keywords -
linear
programming, algorithms, large-scale systems.
|
|
O regresso à fronteira
em optimização linear
Domingos M. Cardoso
Universidade de Aveiro, Departamento de Matemática, 3810-193
Aveiro, Portugal (dcardoso@mat.ua.pt)
Seminário
do Departamento de Matemática Aplicada da Universidade do
Porto, Porto 1994..
Resumo
- O método mais eficiente para a
resolução de problemas de
programação linear foi, durante várias
décadas, o método simplex, desenvolvido por
Dantzig em 1947. Contudo, apesar da grande popularidade deste
método, recentemente têm-se desenvolvido
vários métodos alternativos. Primeiro com a
intenção de melhorar a complexidade
teórica que lhe está associada e, mais
recentemente, motivados pela necessidade crescente de se resolverem, de
um modo eficiente, problemas com cada vez maior dimensão.
Nesta apresentação analisam-se os principais
métodos que se têm revelado como alternativos ao
método simplex, com especial destaque para o
método do elipsoide (Khachiyan, L. G., 1979) e as diferentes
variantes do método de Karmarkar (Karmarkar, N., 1984),
usualmente designadas por métodos de pontos interiores.
Finalmente, faz-se uma abordagem dos non-vertex-simplex-like
methods com maior destaque para o método simplex
generalizado (Cardoso and Clímaco, 1992),
realçando-se os aspectos que motivam a crescente aposta
neste tipo de métodos e/ou nos denominados
métodos híbridos.
Keywords -
linear
programming, non-vertex-simplex like methods, interior point methods.
Referências
- Cardoso, D. M.
and
Clímaco, J. N. The generalized simplex method.
Operations Research Letters, 12 (1992): 337-348.
- Karmarkar, N. A
New polynomial-time algorithm for linear programming.
Combinatorica, 4 (1984): 373-395.
- Khachiyan, L. G. A
polynomial algorithm in linear programming. Soviet
Mathematics Doklady, 20 (1979): 191-194.
|
|
|
|
|
|
|