28 citations · 57 across the 9 of their papers we have counts for
10 papers
Maximum Linear Arrangement: exact algorithms for specific classes of graphs and approximation algorithms for wide classes of graphs
Lluís Alemany-Puig, Juan Luis Esteban, Ramon Ferrer-i-Cancho
Linear arrangements of graphs are a well-known type of graph labeling and are found in many important computational problems. A linear arrangement is usually defined as a permutati…
The expected sum of edge lengths in planar linearizations of trees. Theory and applications
Lluís Alemany-Puig, Ramon Ferrer-i-Cancho
Dependency trees have proven to be a very successful model to represent the syntactic structure of sentences of human languages. In these structures, vertices are words and edges c…
The Maximum Linear Arrangement Problem for trees under projectivity and planarity
Lluís Alemany-Puig, Juan Luis Esteban, Ramon Ferrer-i-Cancho
A linear arrangement is a mapping from the vertices of a graph to distinct consecutive integers. Linear arrangements can be represented by drawing the vertices alon…
The Linear Arrangement Library. A new tool for research on syntactic dependency structures
Lluís Alemany-Puig, Juan Luis Esteban, Ramon Ferrer-i-Cancho
The new and growing field of Quantitative Dependency Syntax has emerged at the crossroads between Dependency Syntax and Quantitative Linguistics. One of the main concerns in this f…
Linear-time calculation of the expected sum of edge lengths in random projective linearizations of trees
Lluís Alemany-Puig, Ramon Ferrer-i-Cancho
The syntactic structure of a sentence is often represented using syntactic dependency trees. The sum of the distances between syntactically related words has been in the limelight…
Minimum projective linearizations of trees in linear time
Lluís Alemany-Puig, Juan Luis Esteban, Ramon Ferrer-i-Cancho
The Minimum Linear Arrangement problem (MLA) consists of finding a mapping from vertices of a graph to distinct integers that minimizes . In t…
The optimality of syntactic dependency distances
Ramon Ferrer-i-Cancho, Carlos Gómez-Rodríguez, Juan Luis Esteban +1
It is often stated that human languages, as other biological systems, are shaped by cost-cutting pressures but, to what extent? Attempts to quantify the degree of optimality of lan…
Reappraising the distribution of the number of edge crossings of graphs on a sphere
Lluís Alemany-Puig, Mercè Mora, Ramon Ferrer-i-Cancho
Many real transportation and mobility networks have their vertices placed on the surface of the Earth. In such embeddings, the edges laid on that surface may cross. In his pioneeri…
Fast calculation of the variance of edge crossings in random arrangements
Lluís Alemany-Puig, Ramon Ferrer-i-Cancho
The crossing number of a graph , , is the minimum number of edge crossings arising when drawing a graph on a certain surface. Determining is a p…
Edge crossings in random linear arrangements
Lluís Alemany-Puig, Ramon Ferrer-i-Cancho
In spatial networks vertices are arranged in some space and edges may cross. When arranging vertices in a 1-dimensional lattice edges may cross when drawn above the vertex sequence…