Can I read Minimal Connected Enclosures on an Embedded Planar Graph on EtoBox?

Minimal Connected Enclosures on an Embedded Planar Graph by Christos Alexopoulos; J.Scott Provan; H.Donald Ratliff; Bryan R. Stutzman is a Computer Science article available to read on EtoBox.

What is Minimal Connected Enclosures on an Embedded Planar Graph about?

We study five problems of finding minimal enclosures comprised of elements of a connected. planar graph with a plane embedding. The first three problems consider the identification uf a shortest enclosing walk. cycle or trail surrounding a polygonal. simply connected obstacle on the plane. We propose polynomial algorithms that improve on existing algorithms. The last two problems consider the formation of minimal zones (sets of adjacent regions such that any pail of points in a zone can be connected by a non-zero width curve that lies entirely in the zone). Specifically. we assume that the regions of the graph have nonnegative weights and seek the formation of minimum weight zones containing a set of points or a set of regions. We prove that the last two problems are NP-hard and transfonn them to Steiner arboresccnce/fixed-charge flow problems.

Who reads Minimal Connected Enclosures on an Embedded Planar Graph?

Author

Christos Alexopoulos; J.Scott Provan; H.Donald Ratliff; Bryan R. Stutzman

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0166-218X)

Published

1999

Language

EN

Field

Computer Science (Physical Sciences)