Antoni Lozano
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Antoni Lozano has a total of 24 co-authors. Here are the top co-authors by number of shared publications:
- Albert Bifet
AI Institute, University of Waikato, Hamilton, Waikato, New Zealand and LTCI, Télécom Paris, IP Paris, Paris, France
2 shared publications - Christoph Dürr
Sorbonne University
2 shared publications Flavio Guíñez
Sauder School of Business
2 shared publications- Gabriel Valiente
Department of Computer Science, Technical University of Catalonia, Barcelona, Spain
2 shared publications - Marek Chrobak
University of California at Riverside
2 shared publications Michal Ziv-Ukelson
Ben Gurion University of the Negev, Beer-Sheva
2 shared publications
Latest Publications
- Open Access
- 10 May 2024
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 355, 122-128
The oriented chromatic number of the hexagonal grid is 6
- 10 May 2024
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 355, 122-128
Open AccessThe oriented chromatic number of the hexagonal grid is 6
- Open Access
Distinguishing Tournaments with Small Label Classes
A $d$-distinguishing vertex (arc) labeling of a digraph is a vertex (arc) labeling using $d$ labels that is not preserved by any nontrivial automorphism. Let $\rho(T)$ ($\rho'(T)$) be the minimum size of a label class in a 2-distinguishing vertex (arc) labeling of a tournament $T$. Gluck's Theorem implies that $\rho(T) \le \lfloor n/2 \rfloor$ for any tournament $T$ of order $n$. In this paper we construct a family of tournaments $\cal H$ such that $\rho(T) \ge \lfloor n/2 \rfloor$ for any order $n$ tournament in $\cal H$. Additionally, we prove that $\rho'(T) \le \lfloor 7n/36 \rfloor + 3$ for any tournament $T$ of order $n$ and $\rho'(T) \ge \lceil n/6 \rceil$ when $T \in {\cal H}$ and has order $n$. These results answer some open questions stated by Boutin.Open AccessDistinguishing Tournaments with Small Label Classes
A $d$-distinguishing vertex (arc) labeling of a digraph is a vertex (arc) labeling using $d$ labels that is not preserved by any nontrivial automorphism. Let $\rho(T)$ ($\rho'(T)$) be the minimum size of a label class in a 2-distinguishing vertex (arc) labeling of a tournament $T$. Gluck's Theorem implies that $\rho(T) \le \lfloor n/2 \rfloor$ for any tournament $T$ of order $n$. In this paper we construct a family of tournaments $\cal H$ such that $\rho(T) \ge \lfloor n/2 \rfloor$ for any order $n$ tournament in $\cal H$. Additionally, we prove that $\rho'(T) \le \lfloor 7n/36 \rfloor + 3$ for any tournament $T$ of order $n$ and $\rho'(T) \ge \lceil n/6 \rceil$ when $T \in {\cal H}$ and has order $n$. These results answer some open questions stated by Boutin. - Open Access
- 7 January 2013
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 20 (1) , P69
Symmetry Breaking in Tournaments
We provide upper bounds for the determining number and the metric dimension of tournaments. A set of vertices $S \subseteq V(T)$ is a determining set for a tournament $T$ if every nontrivial automorphism of $T$ moves at least one vertex of $S$, while $S$ is a resolving set for $T$ if every two distinct vertices in $T$ have different distances to some vertex in $S$. We show that the minimum size of a determining set for an order $n$ tournament (its determining number) is bounded by $\lfloor n/3 \rfloor$, while the minimum size of a resolving set for an order $n$ strong tournament (its metric dimension) is bounded by $\lfloor n/2 \rfloor$. Both bounds are optimal.- 7 January 2013
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 20 (1) , P69
Open AccessSymmetry Breaking in Tournaments
We provide upper bounds for the determining number and the metric dimension of tournaments. A set of vertices $S \subseteq V(T)$ is a determining set for a tournament $T$ if every nontrivial automorphism of $T$ moves at least one vertex of $S$, while $S$ is a resolving set for $T$ if every two distinct vertices in $T$ have different distances to some vertex in $S$. We show that the minimum size of a determining set for an order $n$ tournament (its determining number) is bounded by $\lfloor n/3 \rfloor$, while the minimum size of a resolving set for an order $n$ strong tournament (its metric dimension) is bounded by $\lfloor n/2 \rfloor$. Both bounds are optimal. - Open Access
- 7 April 2012
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 19 (2) , P19
Distinguishing Trees in Linear Time
A graph is said to be $d$-distinguishable if there exists a $d$-labeling of its vertices which is only preserved by the identity map. The distinguishing number of a graph $G$ is the smallest number $d$ for which $G$ is $d$-distinguishable. We show that the distinguishing number of trees and forests can be computed in linear time, improving the previously known $O(n\log n)$ time algorithm.- 7 April 2012
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 19 (2) , P19
Open AccessDistinguishing Trees in Linear Time
A graph is said to be $d$-distinguishable if there exists a $d$-labeling of its vertices which is only preserved by the identity map. The distinguishing number of a graph $G$ is the smallest number $d$ for which $G$ is $d$-distinguishable. We show that the distinguishing number of trees and forests can be computed in linear time, improving the previously known $O(n\log n)$ time algorithm. - 1 December 2011
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 38 (1) , 579-584
Symmetry Breaking in Tournaments
- 1 December 2011
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 38 (1) , 579-584
Symmetry Breaking in Tournaments
- Open Access
- 19 February 2011
- Published by Springer Nature in Algorithmica
- Vol. 64 (2) , 267-278
Tile-Packing Tomography Is $\mathbb{NP}$ -hard- 19 February 2011
- Published by Springer Nature in Algorithmica
- Vol. 64 (2) , 267-278
Open AccessTile-Packing Tomography Is $\mathbb{NP}$ -hard - 1 January 2010
- Published by Springer Nature
- p. 254-263
Tile-Packing Tomography Is ${\mathbb{NP}}$ -hard- 1 January 2010
- Published by Springer Nature
- p. 254-263
Tile-Packing Tomography Is ${\mathbb{NP}}$ -hard- Open Access
- 23 July 2009
- Published by Springer Nature in Machine Learning
- Vol. 78 (1) , 1-33
Mining frequent closed rooted trees
- 23 July 2009
- Published by Springer Nature in Machine Learning
- Vol. 78 (1) , 1-33
Open AccessMining frequent closed rooted trees
- 13 June 2008
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Computational Biology and Bioinformatics
- Vol. 5 (4) , 503-513
Seeded Tree Alignment
The optimal transformation of one tree into another by means of elementary edit operations is an important algorithmic problem that has several interesting applications to computational biology. Here we introduce a constrained form of this problem in which a partial mapping of a set of nodes (the "seeds") in one tree to a corresponding set of nodes in the other tree is given, and present efficient algorithms for both ordered and unordered trees. Whereas ordered tree matching based on seeded nodes has applications in pattern matching of RNA structures, unordered tree matching based on seeded nodes has applications in co-speciation and phylogeny reconciliation. The latter involves the solution of the planar tanglegram layout problem, for which a polynomial-time algorithm is given here.
- 13 June 2008
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Computational Biology and Bioinformatics
- Vol. 5 (4) , 503-513
Seeded Tree Alignment
The optimal transformation of one tree into another by means of elementary edit operations is an important algorithmic problem that has several interesting applications to computational biology. Here we introduce a constrained form of this problem in which a partial mapping of a set of nodes (the "seeds") in one tree to a corresponding set of nodes in the other tree is given, and present efficient algorithms for both ordered and unordered trees. Whereas ordered tree matching based on seeded nodes has applications in pattern matching of RNA structures, unordered tree matching based on seeded nodes has applications in co-speciation and phylogeny reconciliation. The latter involves the solution of the planar tanglegram layout problem, for which a polynomial-time algorithm is given here.
- 1 September 2007
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15294188,p. 499-503
Subtree Testing and Closed Tree Mining Through Natural Representations
Several classical schemes exist to represent trees as strings over a fixed alphabet; these are useful in many algorithmic and conceptual studies. Our previous work has proposed a representation of unranked trees as strings over a countable alphabet, and has shown how this representation is useful for canonizing unordered trees and for mining closed frequent trees, whether ordered or unordered. Here we propose a similar, simpler alternative and adapt some basic algorithmics to it; then we show empirical evidence of the usefulness of this representation for mining frequent closed unordered trees on real-life data.
- 1 September 2007
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15294188,p. 499-503
Subtree Testing and Closed Tree Mining Through Natural Representations
Several classical schemes exist to represent trees as strings over a fixed alphabet; these are useful in many algorithmic and conceptual studies. Our previous work has proposed a representation of unranked trees as strings over a countable alphabet, and has shown how this representation is useful for canonizing unordered trees and for mining closed frequent trees, whether ordered or unordered. Here we propose a similar, simpler alternative and adapt some basic algorithmics to it; then we show empirical evidence of the usefulness of this representation for mining frequent closed unordered trees on real-life data.