| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4949139 | Computational Geometry | 2017 | 7 Pages |
Abstract
Given an outerstring graph and an intersection model consisting of polygonal arcs with a total of N segments, we develop an algorithm that solves the Maximum Weight Independent Set problem in O(N3) time. If the polygonal arcs are restricted to single segments, then outersegment graphs result. For outersegment graphs, we solve the Maximum Weight Independent Set problem in O(n3) time where n is the number of vertices in the graph.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
J. Mark Keil, Joseph S.B. Mitchell, Dinabandhu Pradhan, Martin Vatshelle,