A set $S$ of vertices in a digraph $D=(V,A)$ is a kernel if $S$ is independent and every vertex in $V-S$ has an out-neighbor in $S$. We show that there exist $O(n2^{19.1 \sqrt{k}}+n^4)$-time and $O(2^{19.1 \sqrt{k}} k^9 + n^2)$-time algorithms for checking whether a planar digraph $D$ of order $n$ has a kernel with at … Read more
We propose a new strategy for solving the non-bijective graph matching problem in model-based pattern recognition. The search for the best correspondence between a model and an over-segmented image is formulated as a combinatorial optimization problem, defined by the relational attributed graphs representing the model and the image where recognition has to be performed, together … Read more
We show in this work how the problem of routing and wavelength assignment in all-optical networks may be solved by a combined approach involving the computation of alternative routes for the lightpaths, followed by the solution of a partition coloring problem in a conflict graph. A new tabu search heuristic is also proposed for the … Read more
We describe a graph coloring problem associated with the determination of mathematical derivatives. The coloring instances are obtained as intersection graphs of row partitioned sparse derivative matrices. The size of the graph is dependent on the partition and can be varied between the number of columns and the number of nonzero entries. If solved exactly … Read more
A parallel computational method SDPARA-C is presented for SDPs (semidefinite programs). It combines two methods SDPARA and SDPA-C proposed by the authors who developed a software package SDPA. SDPARA is a parallel implementation of SDPA and it features parallel computation of the elements of the Schur complement equation system and a parallel Cholesky factorization of … Read more
We provide two new, simple proofs of Afriat’s celebrated theorem stating that a finite set of price-quantity observations is consistent with utility maximization if, and only if, the observations satisfy a variation of the Strong Axiom of Revealed Preference known as the Generalized Axiom of Revealed Preference. CitationTechnical Report No. 1381, School of Operations Research … Read more
We propose a new method for non-bijective graph matching for model-based pattern recognition. We formulate the search for the best correspondence between a model and an over-segmented image as a new combinatorial optimization problem, defined by the relational attributed graphs representing the model and the image where recognition has to be performed, together with the … Read more
A phylogenetic tree relates taxonomic units, based on their similarity over a set of characters. We propose a new genetic algorithm for the problem of building a phylogenetic tree under the parsimony criterion. This genetic algorithm makes use of an innovative optimized crossover strategy which is an extension of the path-relinking intensification technique originaly proposed … Read more
We give an algorithm for the following problem: given a graph $G=(V,E)$ with edge-weights and a nonnegative integer $k$, find a minimum cost set of edges that contains $k$ disjoint spanning trees. This also solves the following {\it reinforcement problem}: given a network, a number $k$ and a set of candidate edges, each of them … Read more
Stable multi-sets are an evident generalization of the well-known stable sets. As integer programs, they constitute a general structure which allows for a wide applicability of the results. Moreover, the study of stable multi-sets provides new insights to well-known properties of stable sets. In this paper, we continue our investigations started in Koster and Zymolka … Read more