caa a22 4500 445804564 CHVBK 20180317145152.0 cr unu---uuuuu 170323e20110801xx s 000 0 eng 10.1007/s00453-009-9368-2 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9368-2 Testing Convexity Properties of Tree Colorings [Elektronische Daten] [Eldar Fischer, Orly Yahalom] A coloring of a graph is convex if it induces a partition of the vertices into connected subgraphs. Besides being an interesting property from a theoretical point of view, tests for convexity have applications in various areas involving large graphs. We study the important subcase of testing for convexity in trees. This problem is linked, among other possible applications, with the study of phylogenetic trees, which are central in genetic research, and are used in linguistics and other areas. We give a 1-sided, non-adaptive, distribution-free ε-test for the convexity of tree colorings. The query complexity of our test is O(k/ε), where k is the number of colors, and the additional computational complexity is O(n). On the other hand, we prove a lower bound of $\Omega(\sqrt{k/\epsilon})$ on the query complexity of tests for convexity in the standard model, which applies even for (unweighted) paths. We also consider whether the dependency on k can be reduced in some cases, and provide an alternative testing algorithm for the case of paths. Then we investigate a variant of convexity, namely quasi-convexity, in which all but one of the colors are required to induce connected components. For this problem we provide a 1-sided, non-adaptive ε-test with query complexity O(k/ε 2) and time complexity O(kn/ε). For both our convexity and quasi-convexity tests, we show that, assuming that a query takes constant time, the time complexity can be reduced to a constant independent of n if we allow a preprocessing stage of time O(n) and O(n 2), respectively. Finally, we show how to test for a variation of convexity and quasi-convexity where the maximum number of connectivity classes of each color is allowed to be a constant value other than 1. Springer Science+Business Media, LLC, 2009 Property testing nationallicence Convex coloring nationallicence Sublinear algorithms nationallicence Massively parameterized nationallicence Phylogenetic trees nationallicence Graph algorithms nationallicence Fischer Eldar Computer Science Department, Technion - IIT, 32000, Haifa, Israel aut Yahalom Orly Department of Software Engineering, ORT Braude College, P.O. Box 78, 21982, Karmiel, Israel aut Algorithmica Springer-Verlag 60/4(2011-08-01), 766-805 0178-4617 60:4<766 2011 60 453 https://doi.org/10.1007/s00453-009-9368-2 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9368-2 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Fischer Eldar Computer Science Department, Technion - IIT, 32000, Haifa, Israel aut NATIONALLICENCE 700 1- Yahalom Orly Department of Software Engineering, ORT Braude College, P.O. Box 78, 21982, Karmiel, Israel aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/4(2011-08-01), 766-805 0178-4617 60:4<766 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer