miun.sePublications
Change search
Link to record
Permanent link

Direct link
BETA
Huber, Katharina T
Alternative names
Publications (7 of 7) Show all publications
Cieslik, D., Dress, A., Huber, K. T. & Moulton, V. (2003). Connectivity calculus. Applied Mathematics Letters, 16(3), 395-399
Open this publication in new window or tab >>Connectivity calculus
2003 (English)In: Applied Mathematics Letters, ISSN 0893-9659, E-ISSN 1873-5452, Vol. 16, no 3, p. 395-399Article in journal (Refereed) Published
Abstract [en]

Given a finite hypergraph H = (V, E) and, for each e E E, a collection of nonempty subsets pi(e) of e, Mobius inversion is used to establish a recursive formula for the number of connected components of the hypergraph H = (V, boolean OR(eis an element ofE)pi(e)). As shown elsewhere, this formula is an essential ingredient in the context of a certain divide-and-conquer strategy that allows us to define a dynamical programming scheme solving Steiner's problem for graphs in linear time (however, with a constant depending hyperexponentially on their tree width).

National Category
Mathematics
Identifiers
urn:nbn:se:miun:diva-13652 (URN)000181777900023 ()2-s2.0-84867985841 (Scopus ID)
Available from: 2011-04-19 Created: 2011-04-19 Last updated: 2017-12-11Bibliographically approved
Dress, A., Huber, K. T. & Moulton, V. (2002). An explicit computation of the injective hull of certain finite metric spaces in terms of their associated Buneman complex. Advances in Mathematics, 168(1), 1-28
Open this publication in new window or tab >>An explicit computation of the injective hull of certain finite metric spaces in terms of their associated Buneman complex
2002 (English)In: Advances in Mathematics, ISSN 0001-8708, E-ISSN 1090-2082, Vol. 168, no 1, p. 1-28Article in journal (Refereed) Published
Keywords
Matematik
National Category
Mathematics
Identifiers
urn:nbn:se:miun:diva-13658 (URN)10.1006/aima.2001.2039 (DOI)000176243700001 ()2-s2.0-0036608690 (Scopus ID)
Available from: 2011-04-20 Created: 2011-04-20 Last updated: 2017-12-11Bibliographically approved
Dress, A., Huber, K. T. & Moulton, V. (2002). Antipodal metrics and split systems. European journal of combinatorics (Print), 23(2), 187-200
Open this publication in new window or tab >>Antipodal metrics and split systems
2002 (English)In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 23, no 2, p. 187-200Article in journal (Refereed) Published
Abstract [en]

Recall that a metric d on a finite set X is called antipodal if there exists a map sigma : X --> X: x --> (x) over bar so that d(x, (x) over bar) = d(x, y) + d(y, (x) over bar) holds for all x, y epsilon X. Antipodal metrics canonically arise as metrics induced on specific weighted graphs, although their abundance becomes clearer in light of the fact that any finite metric space can be isometrically embedded in a more or less canonical way into an antipodal metric space called its full antipodal extension. In this paper, we examine in some detail antipodal metrics that are, in addition, totally split decomposable. In particular, we give an explicit characterization of such metrics, and prove that-somewhat surprisingly-the full antipodal extension of a proper metric d on a finite set X is totally split decomposable if and only if d is linear or #X = 3 holds.

National Category
Mathematics
Identifiers
urn:nbn:se:miun:diva-13674 (URN)10.1006/eujc.2001.0556 (DOI)000173869900005 ()2-s2.0-0036110215 (Scopus ID)
Available from: 2011-04-21 Created: 2011-04-21 Last updated: 2017-12-11Bibliographically approved
Bandelt, H. J., Huber, K. T. & Moulton, V. (2002). Quasi-median graphs from sets of partitions. Discrete Applied Mathematics, 122(1-3), 23-35
Open this publication in new window or tab >>Quasi-median graphs from sets of partitions
2002 (English)In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 122, no 1-3, p. 23-35Article in journal (Refereed) Published
Abstract [en]

In studies of molecular evolution, one is typically confronted with the task of inferring a phylogenetic tree from a set X of sequences of length n over a finite alphabet Λ. For studies that invoke parsimony, it has been found helpful to consider the quasi-median graph generated by X in the Hamming graph Λn. Although a great deal is already known about quasi-median graphs (and their algebraic counterparts), little is known about the quasi-median generation in Λn starting from a set X of vertices. We describe the vertices of the quasi-median graph generated by X in terms of the coordinatewise partitions of X. In particular, we clarify when the generated quasi-median graph is the so-called relation graph associated with X. This immediately characterizes the instances where either a block graph or the total Hamming graph is generated. 

National Category
Mathematics
Identifiers
urn:nbn:se:miun:diva-8434 (URN)10.1016/S0166-218X(01)00353-5 (DOI)000176416200003 ()2-s2.0-84867954486 (Scopus ID)
Available from: 2009-01-25 Created: 2009-01-25 Last updated: 2017-12-14Bibliographically approved
Huber, K. T. & Moulton, V. (2002). The relation graph. Paper presented at 4th Slovenian Graph Theory Conference BLED, SLOVENIA, JUN 28-JUL 02, 1999. Discrete Mathematics, 244(1-3), 153-166
Open this publication in new window or tab >>The relation graph
2002 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 244, no 1-3, p. 153-166Article in journal (Refereed) Published
Abstract [en]

Given a set R of distinct, non-trivial partitions of a finite set, we define the relation graph G(R) of R. In case R consists only of bipartitions, G(R) is the well-known Buneman graph, a median graph that has applications in the area of phylogenetic analysis., Here we consider properties of the relation graph for general sets of partitions and, in particular, we see that it mimics the behaviour of the Buneman graph by proving the following two theorems:(i) The graph G(R) is a Hamming graph if and only if R is strongly incompatible.(ii) The graph G(R) is a block graph with #R blocks if and only if R is strongly compatible.

National Category
Mathematics
Identifiers
urn:nbn:se:miun:diva-13675 (URN)10.1016/S0012-365X(01)00080-2 (DOI)000173839800015 ()2-s2.0-31244433852 (Scopus ID)
Conference
4th Slovenian Graph Theory Conference BLED, SLOVENIA, JUN 28-JUL 02, 1999
Note

4th Slovenian Graph Theory Conference, Jun 28-Jul 02, 1999, Bled, Slovenia

Available from: 2011-04-21 Created: 2011-04-21 Last updated: 2017-12-11Bibliographically approved
Huber, K. T., Watson, E. E. & Hendy, M. D. (2001). An algorithm for constructing local regions in a phylogenetic network. Molecular Phylogenetics and Evolution, 19(1), 1-8
Open this publication in new window or tab >>An algorithm for constructing local regions in a phylogenetic network
2001 (English)In: Molecular Phylogenetics and Evolution, ISSN 1055-7903, E-ISSN 1095-9513, Vol. 19, no 1, p. 1-8Article, review/survey (Refereed) Published
Abstract [en]

The groupings of taxa in a phylogenetic tree cannot represent all the conflicting signals that usually occur among site patterns in aligned homologous genetic sequences. Hence a tree-building program must compromise by reporting a subset of the patterns, using some discriminatory criterion. Thus, in the worst case, out of possibly a large number of equally good trees, only an arbitrarily chosen tree might be reported by the tree-building program as “The Tree.” This tree might then be used as a basis for phylogenetic conclusions. One strategy to represent conflicting patterns in the data is to construct a network. The Buneman graph is a theoretically very attractive example of such a network. In particular, a characterization for when this network will be a tree is known. Also the Buneman graph contains each of the most parsimonious trees indicated by the data. In this paper we describe a new method for constructing the Buneman graph that can be used for a generalization of Hadamard conjugation to networks. This new method differs from previous methods by allowing us to focus on local regions of the graph without having to first construct the full graph. The construction is illustrated by an example.

National Category
Mathematics
Identifiers
urn:nbn:se:miun:diva-13598 (URN)10.1006/mpev.2000.0891 (DOI)000168173300001 ()2-s2.0-0034775937 (Scopus ID)
Available from: 2011-04-21 Created: 2011-04-19 Last updated: 2017-12-11Bibliographically approved
Huber, K. T., Moulton, V., Lockhart, P. & Dress, A. (2001). Pruned median networks: A technique for reducing the complexity of median networks. Molecular Phylogenetics and Evolution, 19(2), 302-310
Open this publication in new window or tab >>Pruned median networks: A technique for reducing the complexity of median networks
2001 (English)In: Molecular Phylogenetics and Evolution, ISSN 1055-7903, E-ISSN 1095-9513, Vol. 19, no 2, p. 302-310Article in journal (Refereed) Published
Abstract [en]

Observations from molecular marker studies on recently diverged species indicate that substitution patterns in DNA sequences can often be complex and poorly described by tree-like bifurcating evolutionary models. These observations might result from processes of-species diversification and/or processes of sequence evolution that are not tree-like. In these Cases, bifurcating tree representations provide poor visualization of phylogenetic signals in sequence data. In this paper, we use median networks to study DNA sequence substitution patterns in plant nuclear and chloroplast markers. We describe how to prune median networks to obtain so called pruned median networks. These simpler networks may help to provide a useful framework for investigating the phylogenetic complexity of recently diverged taxa with hybrid origins.

Keywords
phylogenetic network, Buneman graph, lite Buneman graph, median network, pruned median network, split, buttercups, Ranunculus, ITS markers, chloroplast JSA markers
National Category
Mathematics
Identifiers
urn:nbn:se:miun:diva-13591 (URN)10.1006/mpev.2001.0935 (DOI)000168789700012 ()11341811 (PubMedID)2-s2.0-0034777578 (Scopus ID)
Available from: 2011-04-26 Created: 2011-04-19 Last updated: 2017-12-11Bibliographically approved
Organisations

Search in DiVA

Show all publications