Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Minimum bisection is NP-hard on unit disk graphs.

Díaz, J. and Mertzios, G.B. (2014) 'Minimum bisection is NP-hard on unit disk graphs.', in Mathematical foundations of computer science 2014 : 39th international symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, part II. Berlin, Heidelberg: Springer, pp. 251-262. Lecture notes in computer science. (8635).

Abstract

In this paper we prove that the Min-Bisection problem is NP-hard on unit disk graphs, thus solving a longstanding open question.

Item Type:Book chapter
Keywords:Minimum bisection problem, Unit disk graphs, Planar graphs, NP-hardness.
Full text:(AM) Accepted Manuscript
Download PDF
(382Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1007/978-3-662-44465-8_22
Publisher statement:The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-44465-8_22
Date accepted:No date available
Date deposited:17 September 2014
Date of first online publication:2014
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar