bibliography.bib

%------------------------------------ 2024 ------------------------------------%

@phdthesis{Alemany2024b,
	author = {{Alemany-Puig}, {Llu\'{i}s}},
	title = {{Theory, Algorithms and Applications of Arrangements of Graphs: Generation, Expectation and Optimization}},
	school = {Universitat Polit\'ecnica de Catalunya -- Barcelonatech},
	year = {2024},
	url = {}
}

@article{Alemany2024a,
	title = {{The maximum linear arrangement problem for trees under projectivity and planarity}},
	author = {{Alemany-Puig}, {Llu\'{i}s} and {Esteban}, {Juan Luis} and {Ferrer-i-Cancho}, {Ramon}},
	journal = {Information Processing Letters},
	year = {2024},
	volume = {183},
	pages = {106400},
	issn = {0020-0190},
	doi = {10.1016/j.ipl.2023.106400},
	url = {http://arxiv.org/abs/2206.06924},
}

%------------------------------------ 2023 ------------------------------------%

@article{Alemany2023a, 
	title = {{On The Maximum Linear Arrangement Problem for Trees}},
	author = {{Alemany-Puig}, Llu\'{i}s and Esteban, {Juan Luis} and {Ferrer-i-Cancho}, Ramon}, 
	journal = {arXiv},
	arxivId = {2312.04487}, 
	url = {https://arxiv.org/abs/2312.04487}, 
	year = {2023}
}

%------------------------------------ 2022 ------------------------------------%

@article{Alemany2022a,
	title = {{Minimum projective linearizations of trees in linear time}},
	journal = {Information Processing Letters},
	author = {{Alemany-Puig}, Llu\'{i}s and Esteban, {Juan Luis} and {Ferrer-i-Cancho}, Ramon},
	year = {2022},
	volume = {174},
	pages = {106204},
	issn = {0020-0190},
	doi = {10.1016/j.ipl.2021.106204},
	url = {http://arxiv.org/abs/2102.03277}
}

@article{Alemany2022b,
	title = {{Linear-time calculation of the expected sum of edge lengths in projective linearizations of trees}},
	author = {{Alemany-Puig}, Llu\'{i}s and {Ferrer-i-Cancho}, Ramon},
	journal = {Computational Linguistics},
	month = {04},
	year = {2022},
	volume = {48},
	number = {3},
	pages = {491-516},
	issn = {0891-2017},
	doi = {10.1162/coli_a_00442},
	url = {https://arxiv.org/abs/2107.03277}
}

@article{Alemany2022c,
	title = {{Linear-time calculation of the expected sum of edge lengths in planar linearizations of trees}},
	author = {{Alemany-Puig}, Llu\'{i}s and {Ferrer-i-Cancho}, Ramon},
	archivePrefix = {arXiv},
	journal = {Arxiv},
	arxivId = {2207.05564},
	eprint = {2207.05564},
	url = {http://arxiv.org/abs/2207.05564},
	year = {2022}
}

%------------------------------------ 2021 ------------------------------------%

@phdthesis{Anderson2021a,
	author = {Anderson, Mark},
	title = {{An Unsolicited Soliloquy on Dependency Parsing}},
	school = {Universidade da Coru\~na},
	year = {2021},
	url = {https://ruc.udc.es/dspace/bitstream/handle/2183/28513/Anderson_Mark_TD_2021.pdf?sequence=1}
}

@inproceedings{Macutek2021a,
	title = {{The Menzerath-Altmann law in syntactic structure revisited}},
	author = {Ma{\v{c}}utek, J{\'a}n and {\v{C}}ech, Radek and Courtin, Marine},
	booktitle = {Proceedings of the Second Workshop on Quantitative Syntax (Quasy, SyntaxFest 2021)},
	month = 12,
	year = {2021},
	address = {Sofia, Bulgaria},
	publisher = {Association for Computational Linguistics},
	url = {https://aclanthology.org/2021.quasy-1.6},
	pages = {65--73}
}

%------------------------------------ 2020 ------------------------------------%

@article{Alemany2020a,
	title = {{Edge crossings in random linear arrangements}},
	author = {{Alemany-Puig}, Llu\'{i}s and {Ferrer-i-Cancho}, Ramon},
	journal = {Journal of Statistichal Mechanics},
	issue = {2},
	pages = {023403},
	volume = {2020},
	year = {2020},
	doi = {10.1088/1742-5468/ab6845},
	url = {https://arxiv.org/abs/1910.03926}
}

@article{Alemany2020b,
	title = {{Fast calculation of the variance of edge crossings}},
	author = {{Alemany-Puig}, Llu\'{i}s and {Ferrer-i-Cancho}, Ramon},
	archivePrefix = {arXiv},
	journal = {arXiv},
	arxivId = {2003.03258},
	eprint = {2003.03258},
	url = {http://arxiv.org/abs/2003.03258},
	year = {2021}
}

@article{Johnson2020a,
	title = {{The proportion of trees that are linear}},
	author = {Wakhare, Tanay and Wityk, Eric and Johnson, {Charles R.}},
	journal = {Discrete Mathematics},
	volume = {343},
	number = {10},
	pages = {112008},
	year = {2020},
	issn = {0012-365X},
	doi = {10.1016/j.disc.2020.112008},
	url = {https://www.sciencedirect.com/science/article/pii/S0012365X20301941}
}

%------------------------------------ 2019 ------------------------------------%

@MastersThesis{Alemany2019a,
	title = {{Edge crossings in linear arrangements: from theory to algorithms and applications.}},
	author = {{Alemany-Puig}, Llu\'{i}s},
	year = {2019},
	type = {{Master Thesis (M. Sc.)}},
	location = {Barcelona, Spain},
	institution = {Universitat Polit\`ecnica de Catalunya - BarcelonaTech (UPC)},
	publisher = {Universitat Polit\`ecnica de Catalunya - BarcelonaTech (UPC)},
	url = {https://upcommons.upc.edu/handle/2117/168124}
}

@inproceedings{Anderson2019a,
	title = {{Artificially Evolved Chunks for Morphosyntactic Analysis}},
	author = {Anderson, Mark and Vilares, David and {G\'{o}mez-Rodr\'{i}guez}, Carlos},
	booktitle = {Proceedings of the 18th International Workshop on Treebanks and Linguistic Theories (TLT, SyntaxFest 2019)},
	month = 08,
	year = {2019},
	address = {Paris, France},
	publisher = {Association for Computational Linguistics},
	url = {https://aclanthology.org/W19-7815},
	doi = {10.18653/v1/W19-7815},
	pages = {133--143},
}

@article{English2019a,
	title = {{Weighted Tur\'{a}n problems with applications}},
	author = {Bennett, Patrick and English, Sean and {Talanda-Fisher}, Maria},
	journal = {Discrete Mathematics},
	doi = {10.1016/j.disc.2019.04.007},
	issn = {0012365X},
	issue = {8},
	month = {8},
	pages = {2165-2172},
	publisher = {Elsevier B.V.},
	volume = {342},
	year = {2019}
}

@article{Ferrer2019a,
	title = {{The sum of edge lengths in random linear arrangements}},
	author = {{Ferrer-i-Cancho}, Ramon},
	journal = {Journal of Statistichal Mechanics},
	number = {5},
	pages = {053401},
	publisher = {IOP Publishing},
	volume = {2019},
	year = {2019},
	doi = {10.1088/1742-5468/ab11e2}
}

@mastersthesis{Nurse2019a,
	title = {{Maximum linear arrangement of directed graphs}},
	author = {Nurse, Kathryn},
	school = {Simon Fraser University},
	pages = {59},
	year = {2019},
	url = {https://summit.sfu.ca/item/19406}
}

%------------------------------------ 2018 ------------------------------------%

@article{Ferrer2018a,
	title = {{Are crossing dependencies really scarce?}},
	author = {{Ferrer-i-Cancho}, Ramon and {G\'{o}mez-Rodr\'{i}guez}, Carlos and Esteban, {Juan Luis}},
	journal = {Physica A: Statistical Mechanics and its Applications},
	volume = {493},
	pages = {311-329},
	year = {2018},
	doi = {10.1016/j.physa.2017.10.048}
}

@article{Nurse2018a,
	title = {{A Maximum Linear Arrangement Problem on Directed Graphs}},
	journal = {arXiv},
	author = {DeVos, Matt and Nurse, Kathryn},
	year = {2018},
	eprint = {1810.12277},
	archivePrefix = {arXiv},
	primaryClass = {cs.DS}
}

%------------------------------------ 2017 ------------------------------------%

@article{Esteban2017a,
	title = {{A Correction on Shiloach's Algorithm for Minimum Linear Arrangement of Trees}},
	author = {Esteban, {Juan Luis} and {Ferrer-i-Cancho}, Ramon},
	journal = {SIAM Journal on Computing},
	volume = {46},
	number = {3},
	pages = {1146-1151},
	year = {2017},
	doi = {10.1137/15M1046289},
	url = {https://arxiv.org/abs/1511.01061}
}

@inproceedings{Kahane2017a,
	title = {{What are the limitations on the flux of syntactic dependencies? Evidence from UD treebanks}},
	author = {Kahane, Sylvain and Yan, Chunxiao and Botalla, {Marie-Am\'{e}lie}},
	city = {Pisa, Italy},
	booktitle = {Proceedings of the Fourth International Conference on Dependency Linguistics},
	month = {9},
	pages = {73-82},
	url = {https://aclanthology.org/W17-6510},
	year = {2017},
	HAL_ID = {hal-01675325}
}

%------------------------------------ 2015 ------------------------------------%

@article{Futrell2015a,
	title = {{Large-scale evidence of dependency length minimization in 37 languages}},
	author = {Futrell, Richard and Mahowald, Kyle and Gibson, Edward},
	journal = {Proceedings of the National Academy of Sciences},
	volume = {112},
	number = {33},
	pages = {10336--10341},
	year = {2015},
	doi = {10.1073/pnas.1502134112}
}

@inproceedings{Jing2015a,
	title = {{Mean hierarchical distance. Augmenting mean dependency distance}},
	author = {Jing, Yingqi and Liu, Haitao}, 
	year = {2015},
	booktitle = {Proceedings of the Third International Conference on Dependency Linguistics}, 
	pages = {161-170}
}

%------------------------------------ 2014 ------------------------------------%

@article{Ferrer2014a,
	title = {{A stronger null hypothesis for crossing dependencies}},
	author = {{Ferrer-i-Cancho}, Ramon},
	doi = {10.1209/0295-5075/108/58003},
	year = {2014},
	month = {12},
	publisher = {{IOP} Publishing},
	volume = {108},
	number = {5},
	pages = {58003},
	journal = {{EPL} (Europhysics Letters)}
}

%------------------------------------ 2013 ------------------------------------%

@inproceedings{Pitler2013a,
	title = {{Finding Optimal 1-Endpoint-Crossing Trees}},
	author = {Satta, Giorgio and Pitler, Emily and Kannan, Sampath and Marcus, Mitchell},
	booktitle = {Transactions of the Association for Computational Linguistics},
	pages = {13-24},
	url = {https://www.mitpressjournals.org/doi/pdfplus/10.1162/tacl_a_00206},
	year = {2013}
}

%------------------------------------ 2011 ------------------------------------%

@article{Gomez2011a,
	title = {{Dependency Parsing Schemata and Mildly Non-Projective Dependency Parsing}},
	author = {{G\'{o}mez-Rodr\'{i}guez}, Carlos and Carroll, John and Weir, David},
	journal = {Computational Linguistics},
	number = {3},
	pages = {541--586},
	volume = {37},
	year = {2011},
	doi = {10.1162/COLI_a_00060}
}

%------------------------------------ 2010 ------------------------------------%

@article{Liu2010a,
	title = {{Dependency direction as a means of word-order typology: a method based on dependency treebanks}},
	author = {Liu, Haitao},
	journal = {Lingua},
	year = {2010}, 
	volume = {120},
	number = {6},  
	pages = {1567-1578}
}

%------------------------------------ 2007 ------------------------------------%

@inproceedings{Gildea2007a,
	title = {{Optimizing Grammars for Minimum Dependency Length}},
	author = {Gildea, Daniel and Temperley, David},
	booktitle = {Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics},
	month = {06},
	year = {2007},
	address = {Prague, Czech Republic},
	publisher = {Association for Computational Linguistics},
	url = {https://www.aclweb.org/anthology/P07-1024},
	pages = {184--191}
}

%------------------------------------ 2004 ------------------------------------%

@article{Ferrer2004a,
	title = {{Euclidean distance between syntactically linked words}},
	author = {{Ferrer-i-Cancho}, Ramon},
	journal = {Physical Review E},
	issn = {1063651X},
	number = {5},
	pages = {5},
	pmid = {15600720},
	volume = {70},
	year = {2004},
	doi = {10.1103/PhysRevE.70.056135}
}

%------------------------------------ 2003 ------------------------------------%

@article{Hochberg2003a,
	title = {{Optimal one-page tree embeddings in linear time}},
	author = {Hochberg, {Robert A.} and Stallmann, {Matthias F.}},
	journal = {Information Processing Letters},
	volume = {87},
	number = {2},
	pages = {59--66},
	year = {2003},
	issn = {0020-0190},
	doi = {10.1016/S0020-0190(03)00261-8}
}

%------------------------------------ 2001 ------------------------------------%

@book{Cormen2001a,
	title = {{Introduction to Algorithms}},
	address = {Cambridge, MA, USA},
	author = {Cormen, {Thomas H.} and Leiserson, {Charles E.} and Rivest, {Ronald L.} and Stein, Clifford},
	edition = {2nd},
	publisher = {The MIT Press},
	year = {2001}
}

%------------------------------------ 1987 ------------------------------------%

@inproceedings{Iordanskii1987a,
	title = {{Minimal numberings of the vertices of trees --- Approximate approach}},
	author = {Iordanskii, {Mikhail Anatolievich}},
	booktitle = {Fundamentals of Computation Theory},
	editor = {Budach, Lothar and Bukharajev, Rais Gati\v{c} and Lupanov, Oleg Borisovi\v{c}},
	year = {1987},
	publisher = {Springer Berlin Heidelberg},
	address = {Berlin, Heidelberg},
	pages = {214--217},
	isbn = {978-3-540-48138-6}
}

%------------------------------------ 1986 ------------------------------------%

@article{Wright1986a,
	title = {{Constant Time Generation of Free Trees}},
	author = {Wright, Robert Alan and Richmond, Bruce and Odlyzko, Andrew and McKay, {Brendan D.}},
	year = {1986},
	month = {05},
	pages = {540-548},
	volume = {15},
	journal = {SIAM Journal on Computing},
	doi = {10.1137/0215039}
}

%------------------------------------ 1984 ------------------------------------%

@article{Chung1984a,
	title = {{On optimal linear arrangements of trees}},
	author = {Chung, {Fan R. K.}},
	journal = {Computers \& Mathematics with Applications},
	volume = {10},
	number = {1},
	pages = {43--60},
	year = {1984},
	issn = {0898-1221},
	doi = {10.1016/0898-1221(84)90085-3}
}

%------------------------------------ 1981 ------------------------------------%

@article{Colbourn1981a,
	title = {{Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs}},
	author = {Colbourn, {Charles J.} and Booth, {Kellogg S.}},
	journal = {SIAM Journal on Computing},
	volume = {10},
	number = {1},
	pages = {203-225},
	year = {1981},
	doi = {10.1137/0210015}
}

@article{Wilf1981a,
	title = {{The uniform selection of free trees}},
	author = {Wilf, {Herbert S.}},
	year = {1981},
	journal = {Journal of Algorithms}, 
	issn = {0196-6774},
	volume = {2},
	issue = {2},
	pages = {204-207},
	publisher = {Elsevier BV},
	doi = {10.1016/0196-6774(81)90021-3}
}

%------------------------------------ 1980 ------------------------------------%

@article{Beyer1980a,
	author = {Beyer, Terry and Hedetniemi, {Sandra Mitchell}},
	title = {{Constant Time Generation of Rooted Trees}},
	journal = {SIAM Journal on Computing},
	volume = {9},
	number = {4},
	pages = {706-712},
	year = {1980},
	doi = {10.1137/0209055}
}

%------------------------------------ 1979 ------------------------------------%

@article{Shiloach1979a,
	title = {{A Minimum Linear Arrangement Algorithm for Undirected Trees}},
	author = {Shiloach, Yossi},
	journal = {SIAM Journal on Computing},
	volume = {8},
	number = {1},
	pages = {15--32},
	year = {1979},
	doi = {10.1137/0208002}
}

%------------------------------------ 1978 ------------------------------------%

@book{Nijenhuis1978a,
	author = {Nijenhuis, Albert and Wilf, {Herbert S.}},
	title = {{Combinatorial Algorithms: For Computers and Hard Calculators}},
	year = {1978},
	isbn = {0125192606},
	edition = {2nd},
	publisher = {Academic Press, Inc.},
	address = {Orlando, FL, USA},
}

%------------------------------------ 1974 ------------------------------------%

@book{Aho1974a,
	title = {{The Design and Analysis of Computer Algorithms}},
	author = {Aho, {Alfred V.} and Hopcroft, {Jeffrey E.} and Ullman, {John D.}},
	series = {Addison-Wesley series in computer science and information processing},
	year = {1974},
	isbn = {9780201000290},
	edition = {1st},
	publisher = {Addison-Wesley Publishing Company},
	address = {Michigan University}
}

%------------------------------------ 1973 ------------------------------------%

@article{Harary1973a,
	title = {{The number of caterpillars}},
	author = {Harary, Frank and Schwenk, {Allen J.}},
	journal = {Discrete Mathematics},
	issn = {0012365X},
	issue = {4},
	pages = {359--365},
	volume = {6},
	year = {1973},
	doi = {10.1016/0012-365X(73)90067-8}
}

%------------------------------------ 1972 ------------------------------------%

@inbook{Karp1972a,
	title = {{Reducibility among Combinatorial Problems}},
	author = {Karp, {Richard M.}},
	editor = {Miller, {Raymond E.} and Thatcher, {James W.} and Bohlinger, {Jean D.}},
	bookTitle = {{Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 20--22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department}},
	year = {1972},
	publisher = {Springer US},
	address = {Boston, MA},
	pages = {85--103},
	isbn = {978-1-4684-2001-2},
	doi = {10.1007/978-1-4684-2001-2_9}
}

%------------------------------------ 1969 ------------------------------------%

@book{Harary1969a,
	title = {{Graph Theory}},
	author = {Harary, Frank}, 
	year = {1969},
	edition = {2nd},
	publisher = {CRC Press},
	address = {Boca Raton, FL, USA},
}

%------------------------------------ 1948 ------------------------------------%

@article{Otter1948a,
	title = {{Annals of Mathematics The Number of Trees}},
	author = {Otter, Richard},
	number = {3},
	pages = {583--599},
	volume = {49},
	year = {1948},
	doi = {10.2307/1969046},
}

%------------------------------------ 1918 ------------------------------------%

@article{Pruefer1918a,
	title = {{Neuer Beweis eines Satzes \"{u}ber Permutationen}},
	author = {Pr\"{u}fer, Heinz},
	journal = {Arch. Math. Phys}, 
	volume = {27}, 
	pages = {742-744}, 
	year = {1918}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% MISC %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

@misc{OEIS_A000055,
	author = {Sloane, {N. J. A.}},
	title = {{The On-line Encyclopedia of Integer Sequences - A000055 - Number of trees with n unlabeled nodes.}},
	howpublished = {\url{https://oeis.org/A000055}},
	note = {Accessed: 2019-12-28}
}

@misc{OEIS_A000081,
	author = {Sloane, {N. J. A.}},
	title = {{The On-line Encyclopedia of Integer Sequences - A000081 - Number of unlabeled rooted trees with n nodes (or connected functions with a fixed point)}},
	howpublished = {\url{https://oeis.org/A000081}},
	note = {Accessed: 2019-03-31}
}

% Number of k-linear trees
@misc{OEIS_kLinearTrees,
	title = {{The On-Line Encyclopedia of Integer Sequences - A338706 - Number of $2$-linear trees on $n$ nodes.}},
	author = {Sloane, {Neil James Alexander}},
	year = {1964-2022},
	howpublished = {\url{https://oeis.org/A338706}},
	note = {Accessed: 2022-10-07}
}

@misc{GMP_library,
	title = {{The GNU Multiple Precision Arithmetic Library}},
	howpublished = {\url{https://gmplib.org/}},
	note = {Accessed: 2020-03-24}
}

@misc{MathWorld_SpiderGraph,
	title = {{Spider Graph -- Wolfram Math World}},
	howpublished = {\url{https://mathworld.wolfram.com/SpiderGraph.html}},
	note = {Accessed: 2022-10-04}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Manuals

@misc{GiacXcas_Manual,
	author = {Marohnić, Luka},
	year = {2018},
	title = {{Graph theory package for Giac/Xcas - Reference manual}},
	howpublished = {\url{ https://usermanual.wiki/Document/graphtheoryusermanual.346702481/view}},
	note = {Accessed: 2020-01-13},
}