|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 3 van 8 gevonden artikelen
| Titel: |
Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs |
| Auteur: |
Marek Karpinski Miroslaw Kowaluk Andrzej Lingas |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 62 (2004) nr. 3-4 pagina's 369-375 |
| Jaar: |
2004-11-30 |
| Inhoud: |
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. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 3 van 8 gevonden artikelen
| << vorige | volgende >> |