A correction on Shiloach's algorithm for minimum linear arrangement of trees

Inicio | ¿Qué es? | Contacto

English | Català

Consultar RECERCAT

Por comunidades y
colecciones Por fecha Por autores Por títulos Por temas (CDU)

Consultar departamento

Por fecha Por autores Por títulos Por temas (CDU)

Estadisticas

Del documento Todo RECERCAT

Mi RECERCAT

Entrar Alertas por correo-e

Directorio de otros repositorios

RECERCAT Principal > Universitat Politècnica de Catalunya > Documents de recerca > Visualizar documento

Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/106035

dc.contributor	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
dc.contributor	Universitat Politècnica de Catalunya. LOGPROG - Lògica i Programació
dc.contributor	Universitat Politècnica de Catalunya. LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge
dc.contributor.author	Esteban Ángeles, Juan Luis
dc.contributor.author	Ferrer Cancho, Ramon
dc.date	2017-06-29
dc.identifier.citation	Esteban, J. L., Ferrer-i-Cancho, R. A correction on Shiloach's algorithm for minimum linear arrangement of trees. "SIAM journal on computing", 29 Juny 2017, vol. 46, núm. 3, p. 1146-1151.
dc.identifier.citation	0097-5397
dc.identifier.citation	10.1137/15M1046289
dc.identifier.uri	http://hdl.handle.net/2117/106035
dc.language.iso	eng
dc.relation	http://epubs.siam.org/doi/abs/10.1137/15M1046289
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat
dc.subject	Shiloach’s algorithm
dc.title	A correction on Shiloach's algorithm for minimum linear arrangement of trees
dc.type	info:eu-repo/semantics/submittedVersion
dc.type	info:eu-repo/semantics/article
dc.description.abstract	More than 30 years ago, Shiloach published an algorithm to solve the minimum linear arrangement problem for undirected trees. Here we fix a small error in the original version of the algorithm and discuss its effect on subsequent literature. We also improve some aspects of the notation.

Mostrar el registro sencillo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

The scaling of the minimum sum of edge lengths in uniformly random trees

Esteban Ángeles, Juan Luis; Ferrer Cancho, Ramon; Gómez Rodríguez, Carlos

Are crossing dependencies really scarce?

Ferrer Cancho, Ramon; Gómez Rodríguez, Carlos; Esteban Ángeles, Juan Luis

On the complexity of resolution with bounded conjunctions

Esteban Ángeles, Juan Luis; Galesi, Nicola; Messner, Jochen

Automatic detection of at-most-one and exactly-one relations for improved SAT encodings of pseudo-boolean constraints

Ansótegui Gil, Carlos; Bofill Arasa, Miquel; Coll Caballero, Jordi; Dang, Nguyen; Esteban Ángeles, Juan Luis; Miguel, Ian; Nightingale, Peter; Salamon, András Z.; Suy Franch, Josep; Villaret Auselle, Mateu

Exponential separation between tree-like and dag-like Cutting Planes proof systems

Bonet Carbonell, M. Luisa; Esteban Ángeles, Juan Luis; Galesi, Nicola; Johannsen, Jan

Accesibilidad | Aviso legal | Política de Cookies | Documentos de uso interno

Coordinación

Patrocinio