Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Polynomial time approximation schemes for max-bisection on planar and geometric graphs

In English

Författare

Summary, in English

The max-bisection and min-bisection problems are to find a partition of the vertices of a graph into two equal size subsets that, respectively, maximizes or minimizes the number of edges with endpoints in both subsets. We design the first polynomial time approximation scheme for the max-bisection problem on arbitrary planar graphs solving a long-standing open problem. The method of solution involves designing exact polynomial time algorithms for computing optimal partitions of bounded treewidth graphs, in particular max- and min-bisection, which could be of independent interest. Using a similar method we design also the first polynomial time approximation scheme for max-bisection on unit disk graphs ( which could also be easily extended to other geometrically defined graphs).

Avdelning/ar

  • Computer Science

Publiceringsår

2005

Språk

Engelska

Sidor

110-119

Publikation/Tidskrift/Serie

SIAM Journal on Computing

Volym

35

Issue

1

Dokumenttyp

Artikel i tidskrift

Förlag

Society for Industrial and Applied Mathematics

Ämne

  • Computer Science

Nyckelord

  • graph bisection
  • planar graphs
  • combinatorial optimization
  • polynomial time approximation schemes
  • NP-hardness
  • approximation algorithms

Status

Published

Projekt

  • VR 2002-4049

ISBN/ISSN/Övrigt

  • ISSN: 0097-5397