FMFrancisco Javier Zaragoza Martínez

Francisco Javier Zaragoza Martínez

*This is an algorithmically generated author record based on publicly available information.

Francisco Javier Zaragoza Martínez has a total of 55 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    On Grundy indices for complete geometric graphs

    by Dolores Lara, Christian Rubio-Montiel, Francisco Zaragoza

    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

    Constrained many-to-many point matching in two dimensions

    by L. E. Caraballo, R. A. Castro, J. M. Díaz-Báñez, M. A. Heredia, J. Urrutia, I. Ventura, F. J. Zaragoza

    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)$$ 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.

  • Algorithms for the clique problem with multiple-choice constraints under a series–parallel dependency graph

    by Andreas Bärmann, Patrick Gemander, Maximilian Merkert, Ann-Kathrin Wiertz, Francisco Javier Zaragoza Martínez


  • Open Access

    On the Laplacian spectra of token graphs

    by C. Dalfó, F. Duque, R. Fabila-Monroy, M.A. Fiol, C. Huemer, A.L. Trujillo-Negrete, F.J. Zaragoza Martínez


  • Open Access

    On the Laplacian spectra of token graphs

    by C. Dalfó, F. Duque, R. Fabila-Monroy, M. A. Fiol, C. Huemer, A. L. Trujillo-Negrete, F. J. Zaragoza Martínez

    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.

  • Plowing with precedence in polynomial time

    by Rodrigo A. Castro Campos, Cynthia A. Rodríguez Villalobos, Francisco Javier Zaragoza Martínez


  • Postman problems on series–parallel mixed graphs

    by Francisco Javier Zaragoza Martínez

  • Open Access

    On the 2-colored crossing number

    by Oswin Aichholzer, Ruy Fabila-Monroy, Adrian Fuchs, Carlos Hidalgo-Toscano, Irene Parada, Birgit Vogtenhuber, Francisco Zaragoza

    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.

  • Outperforming Several Heuristics for the Multidimensional Assignment Problem

    by Carlos E. Valencia, Carlos A. Alfaro, Francisco Javier Zaragoza Martinez, Marcos Cesar Vargas Magana, Sergio Luis Perez Perezt

    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

    A Step Towards Yuzvinsky's Conjecture

    by Isidoro Gitler, Enrique Reyes, Francisco Javier Zaragoza Martínez

    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$.