Bibliography[1] R., Agarwala, V., Bafna, M., Farach, B., Narayanan, M., Paterson, and M., Thorup. On the approximability of numerical taxonomy (fitting distances by tree metrics). SIAM Journal on Computing, 28:1073–1085, 1999.
[2] A., Aho, Y., Sagiv, T., Szymanski, and J., Ullman. Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM Journal on Computing, 10:405–421, 1981.
[3] I., Althöfer. On optimal realizations of finite metric spaces by graphs. Discrete and Computational Geometry, 3:103–122, 1988.
[4] J., Apresjan. An algorithm for constructing clusters from a distance matrix. Mashinnyi Perevod: Prikladnaja Lingvistika, 9:3–18, 1966.
[5] D., Avis and M., Deza. The cut cone, L1-embeddability, complexity, and multicommodity flows. Networks, 21:595–617, 1991.
[6] H.-J., Bandelt. Recognition of tree metrics. SIAM Journal on Discrete Mathematics, 3:1–6, 1990.
[7] H.-J., Bandelt. Generating median graphs from Boolean matrices. In Y., Dodge, editor, L1-Statistical Analysis and Related Methods, pages 305–309. North-Holland, Amsterdam, 1992.
[8] H.-J., Bandelt. Phylogenetic networks. Verhandlungen des naturwissenschaftlichen Vereins Hamburg, 34:51–57, 1994.
[9] H.-J., Bandelt and A., Dress. Weak hierarchies associated with similarity measures – an additive clustering technique. Bulletin of Mathematical Biology, 51:133–166, 1989.
[10] H.-J., Bandelt and A., Dress. A canonical decomposition theory for metrics on a finite set. Advances in Mathematics, 92:47–105, 1992.
[11] H.-J., Bandelt and A., Dress. Split decomposition: a new and useful approach to phylogenetic analysis of distance data. Molecular Phylogenetics and Evolution, 1:242–252, 1992.
[12] H.-J., Bandelt and A., Dress. A relational approach to split decomposition. In O., Opitz, B., Lausen, and R., Klar, editors, Information and Classification – Concepts, Methods and Applications, pages 123–131. Springer, Berlin, 1993.
[13] H.-J., Bandelt, P., Forster, and A., Rohl. Median-joining networks for inferring intraspecific phylogenies. Molecular Biology and Evolution, 16:37–48, 1999.
[14] H.-J., Bandelt, P., Forster, B. C., Sykes, and M. B., Richards. Mitochondrial portraits of human population using median networks. Genetics, 141:743–753, 1995.
[15] H.-J., Bandelt, K. T., Huber, and V., Moulton. Quasi-median graphs from sets of partitions. Discrete Applied Mathematics, 122:23–35, 2002.
[16] H.-J., Bandelt, H., Mulder, and E., Wilkeit. Quasi-median graphs and algebras. Journal of Graph Theory, 18:681–703, 1994.
[17] H.-J., Bandelt and M., van de Vel. Superextensions and the depth of median graphs. Journal of Combinatorial Theory A, 57:187–202, 1991.
[18] J., Bang-Jensen and G., Gutin. Digraphs: Theory, Algorithms and Applications. Springer-Verlag, Berlin, 2000.
[19] M., Baroni, C., Semple, and M., Steel. A framework for representing reticulate evolution. Annals of Combinatorics, 8:391–408, 2004.
[20] J., Barthélemy. From copair hypergraphs to median graphs with latent vertices. Discrete Mathematics, 76:9–28, 1989.
[21] J., Barthélemy and A., Guenoche. Trees and Proximity Representations. John Wiley, Chichester, 1991.
[22] V., Berry and O., Gascuel. Inferring evolutionary trees with strong combinatorial evidence. Theoretical Computer Science, 240:271–298, 2000.
[23] L. J., Billera, S. P., Holmes, and K., Vogtmann. Geometry of the space of phylogenetic trees. Advances in Applied Mathematics, 27:733–767, 2001.
[24] O., Bininda-Edmonds, editor. Phylogenetic Supertrees: Combining Information to Reveal the Tree of Life. Springer, Berlin, 2004.
[25] A., Björner, M., Las Vergnas, B., Sturmfels, N., White, and G., Ziegler. Oriented matroids. Cambridge University Press, 1999.
[26] S., Böcker. From subtrees to supertrees. PhD thesis, Universität Bielefeld, 1999.
[27] S., Böcker, D., Bryant, A., Dress, and M., Steel. Algorithmic aspects of tree amalgamation. Journal of Algorithms, 37:522–537, 2000.
[28] S., Böcker and A., Dress. A note on maximal hierarchies. Advances in Mathematics, 151:270–282, 2000.
[29] B., Bowditch. Notes on Gromov's hyperbolicity criterion for path metric spaces. In E., Ghyset al., editor, Group Theory from a Geometric Viewpoint, pages 64–167. World Scientific, Singapore, 1991.
[30] M., Bridson and A., Häfliger. Metric Spaces of Non-Positive Curvature. Springer, Berlin, 1999.
[31] D., Bryant. A classification of consensus methods for phylogenies. In M., Janowitz, F.-J., Lapointe, F., McMorris, B., Mirkin, and F., Roberts, editors, BioConsensus, pages 163–184. American Mathematical Society, 2003.
[32] D., Bryant and V., Berry. A structured family of clustering and tree construction methods. Advances in Applied Mathematics, 27:705–732, 2001.
[33] D., Bryant and A., Dress. Linearly independent split systems. European Journal of Combinatorics, 28:1814–1831, 2007.
[34] D., Bryant and V., Moulton. NeighborNet: An agglomerative method for the construction of phylogenetic networks. Molecular Biology and Evolution, 21:255–265, 2004.
[35] D., Bryant, V., Moulton, and A., Spillner. Consistency of the neighbor-net algorithm. Algorithms for Molecular Biology, 2(8), 2007.
[36] P., Buneman. The recovery of trees from measures of dissimilarity. In F., Hodsonet al., editor, Mathematics in the Archaeological and Historical Sciences, pages 387–395. Edinburgh University Press, 1971.
[37] P., Buneman. A note on the metric property of trees. Journal of Combinatorial Theory, Series B, 17:48–50, 1974.
[38] V., Capoyleas and J., Pach. A Turán-type theorem on chords of a convex polygon. Journal of Combinatorial Theory, Series B, 56:9–15, 1992.
[39] ,CGAL, Computational Geometry Algorithms Library. http://www.cgal.org.
[40] W., Chen, A., Dress, and W., Yu. Community structures of networks. Mathematical in Computer Science, 1: 441–457, 2008.
[41] V., Chepoi and B., Fichet. A note on circular decomposable metrics. Geometriae Dedicata, 69:237–240, 1998.
[42] Y., Choe, J., Koolen, K. T., Huber, V., Moulton, and Y., Won. Counting vertices and cubes in median graphs associated to circular split systems. European Journal of Combinatorics, 29:443–456, 2008.
[43] M., Chrobak and L., Larmore. Generosity helps or an 11-competitive algorithm for three servers. Journal of Algorithms, 16:234–263, 1994.
[44] H., Colonius and H. H., Schultze. Trees constructed from empirical relations. Braunschweiger Berichte aus dem Institut für Psychologie, 1, 1977.
[45] H., Colonius and H. H., Schultze. Tree structure from proximity data. British Journal of Mathematical and Statistical Psychology, 34:167–180, 1981.
[46] W., Day. Computational complexity of inferring phylogenies from dissimilarity matrices. Bulletin of Mathematical Biology, 29:461–467, 1987.
[47] C., Devauchelle, A., Dress, A., Grossmann, S., Grünewald, and A., Henaut. Constructing hierarchical set systems. Annals of Combinatorics, 8:441–456, 2004.
[48] M., Deza and M., Laurent. Geometry of Cuts and Metrics. Springer, Berlin, 1997.
[49] R., Diestel. Graph Theory. 3rd edn, Springer, Berlin, 2005.
[50] A., Dress. Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces. Advances in Mathematics, 53:321–402, 1984.
[51] A., Dress. Towards a theory of holistic clustering. In B., Mirkin, F. R., McMorris, F. S., Roberts, and A., Rzhetsky, editors, Mathematical Hierarchies and Biology, pages 271–289. American Mathematical Society, 1997.
[52] A., Dress. The category of X-nets. In J., Feng, J., Jost, and M., Qian, editors, Networks: From Biology to Theory, pages 3–22. Springer, Berlin, 2007.
[53] A., Dress, T., Wu, and X., Xu. A note on single-linkage equivalence. Applied Mathematics Letters, 23:432–435, 2010.
[54] A., Dress and P. L., Erdős. X-trees and weighted quartet systems. Annals of Combinatorics, 7:155–169, 2003.
[55] A., Dress, M., Hendy, K. T., Huber, and V., Moulton. On the number of vertices and edges in the Buneman graph. Annals of Combinatorics, 1:329–337, 1997.
[56] A., Dress, B., Holland, K. T., Huber, J., Koolen, V., Moulton, and J., Weyer-Menkhoff. Delta additive and delta ultra-additive maps, Gromov's trees, and the Farris transform. Discrete Applied Mathematics, 146:51–73, 2005.
[57] A., Dress, K. T., Huber, J., Koolen, and V., Moulton. Blocks and cut vertices of the Buneman graph, 2011. Submitted.
[58] A., Dress, K. T., Huber, A., Lesser, and V., Moulton. Hereditarily optimal realizations of consistent metrics. Annals of Combinatorics, 10:63–76, 2006.
[59] A., Dress, K. T., Huber, and V., Moulton. Some variations on a theme by Buneman. Annals of Combinatorics, 1:339–352, 1997.
[60] A., Dress, K. T., Huber, and V., Moulton. A comparison between two distinct continuous models in projective cluster theory: The median and the tight-span construction. Annals of Combinatorics, 2:299–311, 1998.
[61] A., Dress, K. T., Huber, and V., Moulton. Hereditarily optimal realizations: Why are they relevant in phylogenetric analysis and how does one compute them? In Proceedings of the Euroconference, Algebraic Combinatorics and Applications, pages 110–117. Springer, Berlin, 2001.
[62] A., Dress, K. T., Huber, and V., Moulton. An explicit computation of the injective hull of certain finite metric spaces in terms of their associated Buneman complex. Advances in Mathematics, 168:1–28, 2002.
[63] A., Dress, K. T., Huber, and V., Moulton. Some uses of the Farris transform in mathematics and phylogenetics – A review. Annals of Combinatorics, 11:1–37, 2007.
[64] A., Dress and D., Huson. Constructing split graphs. IEEE Transactions on Computational Biology and Bioinformatics, 1:109–115, 2004.
[65] A., Dress, D., Huson, and V., Moulton. Analyzing and visualizing distance data using SplitsTree. Discrete Applied Mathematics, 71:95–110, 1996.
[66] A., Dress, J., Koolen, and V., Moulton. On line arrangements in the hyperbolic plane. European Journal of Combinatorics, 23:549–557, 2002.
[67] A., Dress, J., Koolen, and V., Moulton. 4n – 10. Annals of Combinatorics, 8:463–471, 2004.
[68] A., Dress and R., Scharlau. Gated sets in metric spaces. Aequationes Mathematicae, 34:112–120, 1987.
[69] J., Elson, C., Herrnstadt, G., Preston, L., Thal, C., Morris, J., Edwardson, M., Beal, D., Turnbull, and N., Howell. Does the mitochondrial genome play a role in the etiology of Alzheimer's disease? Human Genetics, 119:241–254, 2006.
[70] A., Erné, J., Koslowski, A., Melton, and G., Strecker. A primer on Galois connections. Annals of the New York Academy of Sciences, 704:103–125, 1993.
[71] G., Estabrook. Fifty years of character compatibility concepts at work. Journal of Systematics and Evolution, 46:109–129, 2008.
[72] M., Farach, S., Kannan, and T., Warnow. A robust model for finding optimal evolutionary trees. Algorithmica, 13:155–179, 1995.
[73] J., Farris. On the phenetic approach to vertebrate classification. In M., Hecht, P., Goody, and B., Hecht, editors, Major Patterns in Vertebrate Evolution, pages 823–850. Plenum Press, New York, 1977.
[74] J., Farris. The information content of the phylogenetic system. Systematic Zoology, 28:483–519, 1979.
[75] J. S., Farris, A. G., Kluge, and M. J., Eckardt. A numerical approach to phylogenetic systematics. Systematic Zoology, 19:172–189, 1970.
[76] J., Felsenstein. Inferring Phylogenies. Sinauer Associates, Sunderland MA, 2004.
[77] S., Finnilä, I., Hassinen, L., Ala-Kokko, and K., Majamma. Phylogenetic network of the mtDNA haplogroup U in northern Finland based on sequence analysis of the complete coding region by conformation-sensitive gel electrophoresis. American Journal of Human Genetics, 66:1017–1026, 2000.
[78] A., Frank, A., Karzanov, and A., Sebő. On integer multiflow maximization. SIAM Journal on Discrete Mathematics, 10:158–170, 1997.
[79] M., Garey and D., Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979.
[80] E., Gawrilow and M., Joswig. Geometric reasoning with polymake, 2005. arXiv:math.CO/0507273.
[81] M., Girvan and M., Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America, 99:7821–7826, 2002.
[82] M., Gromov. Hyperbolic groups. In Essays in Group Theory, volume 8 of MSRI. Springer, Berlin, 1988.
[83] M., Gromov. CAT(κ)-spaces: construction and concentration. Journal of Mathematical Sciences, 119:178–200, 2004.
[84] S., Grünewald. Slim sets of binary trees. Journal of Combinatorial Theory A, 2011. to appear.
[85] S., Grünewald, K., Forslund, A., Dress, and V., Moulton. QNet: An agglomerative method for the construction of phylogenetic networks from weighted quartets. Molecular Biology and Evolution, 24:532–538, 2007.
[86] S., Grünewald, K. T., Huber, V., Moulton, C., Semple, and A., Spillner. Characterizing weak compatibility in terms of weighted quartets. Advances in Applied Mathematics, 42:329–341, 2009.
[87] S., Grünewald, K. T., Huber, V., Moulton, and C., Semple. Encoding phylogenetic trees in terms of weighted quartets. Journal of Mathematical Biology, 56:465–477, 2008.
[88] S., Grünewald, J., Koolen, and W., Lee. Quartets in maximal weakly compatible split systems. Applied Mathematics Letters, 22:1604–1608, 2009.
[89] S., Grünewald, V., Moulton, and A., Spillner. Consistency of the Qnet algorithm for generating planar split graphs from weighted quartets. Discrete Applied Mathematics, 157:2325–2334, 2009.
[90] S. L., Hakimi and S. S., Yau. Distance matrix of a graph and its realizability. Quarterly of Applied Mathematics, 22:305–317, 1964.
[91] M. D., Hendy. The relationship between simple evolutionary tree models and observable sequence data. Systematic Zoology, 38:310–321, 1989.
[92] M. D., Hendy and D., Penny. A framework for the quantitative study of evolutionary trees. Systematic Zoology, 38:297–309, 1989.
[93] M. D., Hendy and D., Penny. Spectral analysis of phylogenetic data. Journal of Classification, 10:5–24, 1993.
[94] S., Herrmann and M., Joswig. Bounds on the f-vectors of tight spans. Contributions to Discrete Mathematics, 2:161–184, 2007.
[95] B., Holland, G., Conner, K. T., Huber, and V., Moulton. Imputing supertrees and supernetworks from quartets. Systematic Biology, 56:57–67, 2007.
[96] B., Holland, F., Delsuc, and V., Moulton. Visualizing conflicting evolutionary hypotheses in large collections of trees using consensus networks. Systematic Biology, 54:66–76, 2005.
[97] K. T., Huber, V., Moulton, P., Lockhart, and A., Dress. Pruned median networks: a technique for reducing the complexity of median networks. Molecular Phylogenetics and Evolution, 19:302–310, 2001.
[98] D., Huson. SplitsTree: analyzing and visualizing evolutionary data. Bioinformatics, 14:68–73, 1998.
[99] D., Huson, T., Dezulian, T., Klöpper, and M., Steel. Phylogenetic super-networks from partial trees. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 1:151–158, 2004.
[100] D., Huson and R., Rupp. Summarizing multiple gene trees using cluster networks. In Workshop on Algorithms in Bioinformatics, volume 5251 of LNCS, pages 296–305. Springer, Berlin, 2008.
[101] W., Imrich and S., Klavžar. Product Graphs: Structure and Recognition. John Wiley, New York, 2000.
[102] W., Imrich, J., Simoes-Pereira, and C., Zamfirescu. On optimal embeddings of metrics in graphs. Journal of Combinatorial Theory, Series B, 36:1–15, 1984.
[103] J., Isbell. Six theorems about metric spaces. Commentarii Mathematici Helvetici, 39:65–74, 1964.
[104] J., Jansson and W.-K., Sung. Inferring a level-1 phylogenetic network from a dense set of rooted triplets. Theoretical Computer Science, 363:60–68, 2006.
[105] G., Kalai. Polytope skeletons and paths. In J., Goodman and J., O'Rourke, editors, Handbook of Discrete and Computational Geometry, pages 455–476. Chapman & Hall/CRC Press, Boca Raton, 2004.
[106] K., Kalmanson. Edgeconvex circuits and the travelling salesman problem. Canadian Journal of Mathematics, 27:1000–1010, 1975.
[107] A., Karzanov and M., Lomonosov. Systems of flows in undirected networks. In O., Larichev, editor, Mathematical Programming, volume 1. Institute for Systems Studies, 1978. In Russian.
[108] S., Klavžar and H., Mulder. Median graphs: characterizations, location theory and related structures. Journal of Combinatorial Mathematics and Combinatorial Computing, 30:103–127, 1999.
[109] M., Kotetishvili, O., Stine, A., Kreger, J., Morris, and A., Sulakvelidze. Multilocus sequence typing for characterization of clinical and environmental Salmonella strains. Journal of Clinical Microbiology, 40:1626–1635, 2002.
[110] M., Lomonosov. Combinatorial approaches to multiflow problems. Discrete Applied Mathematics, 11:1–93, 1985.
[111] F., MacWilliams and N., Sloane. The Theory of Error-Correcting Codes. North-Holland, Amsterdam, 1983.
[112] T., Margush and F., McMorris. Consensus n-trees. Bulletin of Mathematical Biology, 43:239–244, 1981.
[113] C., Meacham. Theoretical and computational considerations of the compatibility of qualitative taxonomic characters. In J., Felsenstein, editor, Numerical Taxonomy, pages 304–314. Springer, Berlin, 1983.
[114] V., Moulton and M., Steel. Retractions of finite distance functions onto tree metrics. Discrete Applied Mathematics, 91:215–233, 1999.
[115] H., Mulder. The interval function of a graph. Mathematical Centre Tracts, 132. Mathematisch Centrum, Amsterdam, 1980.
[116] M., Newman. Finding community structure in networks using the eigenvectors of matrices. Physical Review E, 74, 036104, 2006.
[117] J., Neyman. Molecular studies of evolution: a source of novel statistical problems. In S., Gupta and J., Yackel, editors, Statistical Decision Theory and Related Topics, pages 1–27. Academic Press, New York, 1971.
[118] M., Owen and J., Provan. A fast algorithm for computing geodesic distances in tree space. IEEE Transactions on Computational Biology and Bioinformatics, 8:2–13, 2011.
[119] R., Rammal, J., Angles d'Auriac, and B., Doucot. On the degree of ultrametricity. Le Journal de Physique-Lettre, 46:945–952, 1985.
[120] N., Saitou and M., Nei. The neighbor-joining method: A new method for reconstructing phylogenetic trees. Molecular Biology and Evolution, 4:406–425, 1987.
[121] J. M. S., Simões-Pereira. A note on the tree realizability of a distance matrix. Journal of Combinatorial Theory, 6:303–310, 1969.
[122] J. M. S., Simões-Pereira and C. M., Zamfirescu. Submatrices of non-treerealizable distance matrices. Linear Algebra and its Applications, 44:1–17, 1982.
[123] M., Steel. The complexity of reconstructing trees from qualitative characters and subtrees. Journal of Classification, 9:91–116, 1992.
[124] K., Strimmer and A., von Haeseler. Quartet puzzling: A quartet maximum likelihood method for reconstructing tree topologies. Molecular Biology and Evolution, 13:964–969, 1996.
[125] B., Sturmfels and J., Yu. Classification of six-point metrics. The Electronic Journal of Combinatorics, 11, 2004.
[126] T-H., To and M., Habib. Level-k phylogenetic network can be constructed from a dense triplet set in polynomial time. In Annual Symposium on Combinatorial Pattern Matching, LNCS. Springer, Berlin, 2009.
[127] L., van Iersel, J., Keijsper, S., Kelk, L., Stougie, F., Hagen, and T., Boekhout. Constructing level-2 phylogenetic networks from triplets. In Annual International Conference on Research in Computational Molecular Biology, volume 4955 of LNCS, pages 450–462. Springer, Berlin, 2008.
[128] J., van Lint. Introduction to Coding Theory. 3rd edn, Springer, Berlin, 1999.
[129] A., Verbeek. Superextensions of topological spaces. Mathematical Centre Tracts, 41, 1972.
[130] R., Wetzel. Zur Visualisierung abstrakter Ähnlichkeitsbeziehungen. PhD thesis, Universität Bielefeld, 1995.
[131] J., Weyer-Menkhoff. New quartet methods in phylogenetic combinatorics. PhD thesis, Universität Bielefeld, 2003.
[132] J., Weyer-Menkhoff, C., Devauchelle, A., Grossmann, and S., Grünewald. Integer linear programming as a tool for constructing trees from quartet data. Computational Biology and Chemistry, 29:196–203, 2005.
[133] E., Wilkeit. The retracts of Hamming graphs. Discrete Mathematics, 102:197–218, 1992.
[134] P., Winkler. Isometric embeddings in products of complete graphs. Discrete Applied Mathematics, 7:221–225, 1984.
[135] P., Winkler. The complexity of metric realisation. SIAM Journal of Discrete Mathematics, 1:552–559, 1988.
[136] K. A., Zaretskii. Constructing trees from the set of distances between pendant vertices. Uspehi Matematiceskih Nauk, 20:90–92, 1965.
