Francisco Javier Zaragoza Martínez
Francisco Javier Zaragoza Martínez has a total of 55 co-authors. Here are the top co-authors by number of shared publications:
- Rodrigo Alexander Castro Campos
Universidad Autonoma Metropolitana Azcapotzalco
5 shared publications - Ana Laura Trujillo-Negrete
Instituto de Matematicas Universidad Nacional Autónoma de México Mexico City Mexico
2 shared publications - Carlos E. Valencia
Centro de Investigación y de Estudios Avanzados del IPN
2 shared publications - Cristina Dalfo
Departament de Matemàtica, Universitat de Lleida, Igualada (Barcelona), Catalonia
2 shared publications - Marco Antonio Heredia Velasco
Universidad Autónoma Metropolitana Unidad Azcapotzalco
2 shared publications - Rafael López Bracho
Universidad Autónoma Metropolitana Azcapotzalco, Departamento de Sistemas
2 shared publications
Latest Publications
- Open Access
On Grundy indices for complete geometric graphs
The pseudo-Grundy index of a graph is the largest number of colors that can be assigned to its edges, such that for every pair of colors $i,j$, if $i < j$ then every edge colored with color $j$ is adjacent to at least one edge colored with color $i$. This index has been widely studied. A geometric graph is a graph drawn in the plane such that its vertices are points in general position, and its edges are straight-line segments. In this paper, we extend the notion of pseudo-Grundy index for geometric graphs, and present results for complete geometric graphs.Open AccessOn Grundy indices for complete geometric graphs
The pseudo-Grundy index of a graph is the largest number of colors that can be assigned to its edges, such that for every pair of colors $i,j$, if $i < j$ then every edge colored with color $j$ is adjacent to at least one edge colored with color $i$. This index has been widely studied. A geometric graph is a graph drawn in the plane such that its vertices are points in general position, and its edges are straight-line segments. In this paper, we extend the notion of pseudo-Grundy index for geometric graphs, and present results for complete geometric graphs. - Open Access
- 26 January 2024
- Published by Springer Nature in Optimization Letters
- Vol. 18 (8) , 1837-1854
Constrained many-to-many point matching in two dimensions
In the minimum-weight many-to-many point matching problem, we are given a set R of red points and a set B of blue points in the plane, of total size N, and we want to pair up each point in R to one or more points in B and vice versa so that the sum of distances between the paired points is minimized. This problem can be solved in $$O(N^3)$$ time by using a reduction to the minimum-weight perfect matching problem, and thus, it is not fast enough to be used for on-line systems where a large number of tunes need to be compared. Motivated by similarity problems in music theory, in this paper we study several constrained minimum-weight many-to-many point matching problems in which the allowed pairings are given by geometric restrictions, i.e., a bichromatic pair can be matched if and only if the corresponding points satisfy a specific condition of closeness. We provide algorithms to solve these constrained versions in O(N) time when the sets R and B are given ordered by abscissa.- 26 January 2024
- Published by Springer Nature in Optimization Letters
- Vol. 18 (8) , 1837-1854
Open AccessConstrained many-to-many point matching in two dimensions
In the minimum-weight many-to-many point matching problem, we are given a set R of red points and a set B of blue points in the plane, of total size N, and we want to pair up each point in R to one or more points in B and vice versa so that the sum of distances between the paired points is minimized. This problem can be solved in $$O(N^3)$$ time by using a reduction to the minimum-weight perfect matching problem, and thus, it is not fast enough to be used for on-line systems where a large number of tunes need to be compared. Motivated by similarity problems in music theory, in this paper we study several constrained minimum-weight many-to-many point matching problems in which the allowed pairings are given by geometric restrictions, i.e., a bichromatic pair can be matched if and only if the corresponding points satisfy a specific condition of closeness. We provide algorithms to solve these constrained versions in O(N) time when the sets R and B are given ordered by abscissa. - 19 October 2022
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 324, 145-166
Algorithms for the clique problem with multiple-choice constraints under a series–parallel dependency graph
- 19 October 2022
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 324, 145-166
Algorithms for the clique problem with multiple-choice constraints under a series–parallel dependency graph
- Open Access
- 1 September 2021
- Published by Elsevier in Linear Algebra and its Applications
- Vol. 625, 322-348
On the Laplacian spectra of token graphs
- 1 September 2021
- Published by Elsevier in Linear Algebra and its Applications
- Vol. 625, 322-348
Open AccessOn the Laplacian spectra of token graphs
- Open Access
On the Laplacian spectra of token graphs
We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The $k$-token graph $F_k(G)$ of a graph $G$ is the graph whose vertices are the $k$-subsets of vertices from $G$, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in $G$. In this paper, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers $h$ and $k$ such that $1\le h\le k\le \frac{n}{2}$, the Laplacian spectrum of $F_h(G)$ is contained in the Laplacian spectrum of $F_k(G)$. We also show that the double odd graphs and doubled Johnson graphs can be obtained as token graphs of the complete graph $K_n$ and the star $S_{n}=K_{1,n-1}$, respectively. Besides, we obtain a relationship between the spectra of the $k$-token graph of $G$ and the $k$-token graph of its complement $\overline{G}$. This generalizes a well-known property for Laplacian eigenvalues of graphs to token graphs. Finally, the double odd graphs and doubled Johnson graphs provide two infinite families, together with some others, in which the algebraic connectivities of the original graph and its token graph coincide. Moreover, we conjecture that this is the case for any graph $G$ and its token graph.Open AccessOn the Laplacian spectra of token graphs
We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The $k$-token graph $F_k(G)$ of a graph $G$ is the graph whose vertices are the $k$-subsets of vertices from $G$, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in $G$. In this paper, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers $h$ and $k$ such that $1\le h\le k\le \frac{n}{2}$, the Laplacian spectrum of $F_h(G)$ is contained in the Laplacian spectrum of $F_k(G)$. We also show that the double odd graphs and doubled Johnson graphs can be obtained as token graphs of the complete graph $K_n$ and the star $S_{n}=K_{1,n-1}$, respectively. Besides, we obtain a relationship between the spectra of the $k$-token graph of $G$ and the $k$-token graph of its complement $\overline{G}$. This generalizes a well-known property for Laplacian eigenvalues of graphs to token graphs. Finally, the double odd graphs and doubled Johnson graphs provide two infinite families, together with some others, in which the algebraic connectivities of the original graph and its token graph coincide. Moreover, we conjecture that this is the case for any graph $G$ and its token graph. - 1 May 2020
- Published by Elsevier in Operations Research Letters
- Vol. 48 (3) , 266-270
Postman problems on series–parallel mixed graphs
- 1 May 2020
- Published by Elsevier in Operations Research Letters
- Vol. 48 (3) , 266-270
Postman problems on series–parallel mixed graphs
- Open Access
On the 2-colored crossing number
Let $D$ be a straight-line drawing of a graph. The rectilinear 2-colored crossing number of $D$ is the minimum number of crossings between edges of the same color, taken over all possible 2-colorings of the edges of $D$. First, we show lower and upper bounds on the rectilinear 2-colored crossing number for the complete graph $K_n$. To obtain this result, we prove that asymptotic bounds can be derived from optimal and near-optimal instances with few vertices. We obtain such instances using a combination of heuristics and integer programming. Second, for any fixed drawing of $K_n$, we improve the bound on the ratio between its rectilinear 2-colored crossing number and its rectilinear crossing number.Open AccessOn the 2-colored crossing number
Let $D$ be a straight-line drawing of a graph. The rectilinear 2-colored crossing number of $D$ is the minimum number of crossings between edges of the same color, taken over all possible 2-colorings of the edges of $D$. First, we show lower and upper bounds on the rectilinear 2-colored crossing number for the complete graph $K_n$. To obtain this result, we prove that asymptotic bounds can be derived from optimal and near-optimal instances with few vertices. We obtain such instances using a combination of heuristics and integer programming. Second, for any fixed drawing of $K_n$, we improve the bound on the ratio between its rectilinear 2-colored crossing number and its rectilinear crossing number. - 1 September 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-6
Outperforming Several Heuristics for the Multidimensional Assignment Problem
The multidimensional assignment problem (MAP), also known as multi-index assignment problem, is a natural extension of the assignment problem. A MAP deals with the question of how to assign elements from s disjoint sets with n 1 ,...,n s items on each. A MAP with s dimensions is called a sAP. Local search heuristics and Memetic algorithms have been proven to be the most effective techniques to solve MAP. In this work we use an exact technique that outperforms some local searches and Memetic algorithms on several instances of MAP. Then, we design a heuristic that uses repeatedly our exact technique in order to provide high quality solutions for harder types of instances of MAP. We perform an experimental evaluation of our exact technique and of our heuristic and we show its effectiveness against more complex local searches and some Memetic algorithms for MAP.
- 1 September 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-6
Outperforming Several Heuristics for the Multidimensional Assignment Problem
The multidimensional assignment problem (MAP), also known as multi-index assignment problem, is a natural extension of the assignment problem. A MAP deals with the question of how to assign elements from s disjoint sets with n 1 ,...,n s items on each. A MAP with s dimensions is called a sAP. Local search heuristics and Memetic algorithms have been proven to be the most effective techniques to solve MAP. In this work we use an exact technique that outperforms some local searches and Memetic algorithms on several instances of MAP. Then, we design a heuristic that uses repeatedly our exact technique in order to provide high quality solutions for harder types of instances of MAP. We perform an experimental evaluation of our exact technique and of our heuristic and we show its effectiveness against more complex local searches and some Memetic algorithms for MAP.
- Open Access
- 5 October 2017
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 24 (4) , P4.28
A Step Towards Yuzvinsky's Conjecture
An intercalate matrix $M$ of type $[r,s,n]$ is an $r\times s$ matrix with entries in $\{1,2,\dotsc,n\}$ such that all entries in each row are distinct, all entries in each column are distinct, and all $2 \times 2$ submatrices of $M$ have either $2$ or $4$ distinct entries. Yuzvinsky's Conjecture on intercalate matrices claims that the smallest $n$ for which there is an intercalate matrix of type $[r,s,n]$ is the Hopf-Stiefel function $r \circ s$. In this paper we prove that Yuzvinsky's Conjecture is asimptotically true for $\frac{5}{6}$ of integer pairs $(r,s)$. We prove the Conjecture for $r\le 8$, and we study it in the range $r,s\le 32$.- 5 October 2017
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 24 (4) , P4.28
Open AccessA Step Towards Yuzvinsky's Conjecture
An intercalate matrix $M$ of type $[r,s,n]$ is an $r\times s$ matrix with entries in $\{1,2,\dotsc,n\}$ such that all entries in each row are distinct, all entries in each column are distinct, and all $2 \times 2$ submatrices of $M$ have either $2$ or $4$ distinct entries. Yuzvinsky's Conjecture on intercalate matrices claims that the smallest $n$ for which there is an intercalate matrix of type $[r,s,n]$ is the Hopf-Stiefel function $r \circ s$. In this paper we prove that Yuzvinsky's Conjecture is asimptotically true for $\frac{5}{6}$ of integer pairs $(r,s)$. We prove the Conjecture for $r\le 8$, and we study it in the range $r,s\le 32$.