Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs

Karpinski M., Kowaluk M., Lingas A.

Fundamenta Informaticae

2004

Vol. 62, nr 3,4

369--375

The max-bisection problem is to find a partition of the vertices of a graph into two equal size subsets that maximizes the number of edges with endpoints in both subsets. We obtain new improved approximation ratios for the max-bisection problem on the low degree k-regular graphs for 3 ≤ k Ł≤8, by deriving some improved transformations from a maximum cut into a maximum bisection. In the case of three regular graphs we obtain an approximation ratio of 0.854, and in the case of four and five regular graphs, approximation ratios of 0.805, and 0.812, respectively.

A Fast Algorithm for Optimal Alignment between Similar Ordered Trees

Jansson J., Lingas A.

Fundamenta Informaticae

2003

Vol. 56, nr 1,2

105-120

We present a fast algorithm for optimal alignment between two similar ordered trees with node labels. Let S and T be two such trees with |S| and |T| nodes, respectively. If there exists an optimal alignment between S and T which uses at most d blank symbols and d is known in advance, it can be constructed in O(n logn ź(maxdeg)3 źd2) time, where n = max{|S|,|T|} and maxdeg is the maximum degree of all nodes in S and T. If d is not known in advance, we can construct an optimal alignment in O(n logn ź(maxdeg)3źf2) time, where f is the difference between the highest possible score for any alignment between two trees having a total of |S| + |T| nodes and the score of an optimal alignment between S and T, if the scoring scheme satisfies some natural assumptions. In particular, if the degrees of both input trees are bounded by a constant, the running times reduce to O(n logn źd2) and O(n logn źf2), respectively.