On the parallel complexity of degree sequence problems

Arikati, Srinivasa

Local TagsRelease HistoryDetailsSummary

On the parallel complexity of degree sequence problems

Arikati, S.(1994). On the parallel complexity of degree sequence problems (MPI-I-1994-162). Saarbrücken: Max-Planck-Institut für Informatik.

Item is Released

show all hide all

Basic

show hide

Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-B695-6 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-B69F-1

Genre: Report

Files

show Files

hide Files

:

MPI-I-94-162.pdf (Any fulltext), 190KB

View Save

File Permalink:
https://hdl.handle.net/11858/00-001M-0000-0014-B697-2

Name:
MPI-I-94-162.pdf

Description:
-

OA-Status:

Visibility:
Public

MIME-Type / Checksum:
application/pdf / [MD5]

Technical Metadata:

View

Copyright Date:
-

Copyright Info:
-

License:
-

Locators

show

Creators

show

hide

Creators:
Arikati, Srinivasa¹, Author

Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019

Content

show

hide

Free keywords: -

Abstract: We describe a robust and efficient implementation of the Bentley-Ottmann sweep line algorithm based on the LEDA library of efficient data types and algorithms. The program computes the planar graph $G$ induced by a set $S$ of straight line segments in the plane. The nodes of $G$ are all endpoints and all proper intersection points of segments in $S$. The edges of $G$ are the maximal relatively open subsegments of segments in $S$ that contain no node of $G$. All edges are directed from left to right or upwards. The algorithm runs in time $O((n+s) log n)$ where $n$ is the number of segments and $s$ is the number of vertices of the graph $G$. The implementation uses exact arithmetic for the reliable realization of the geometric primitives and it uses floating point filters to reduce the overhead of exact arithmetic.

Details

show

hide

Language(s): eng - English

Dates: Date issued: 1994

Publication Status: Issued

Pages: 12 p.

Publishing info: Saarbrücken : Max-Planck-Institut für Informatik

Table of Contents: -

Rev. Type: -

Identifiers: Report Nr.: MPI-I-1994-162
BibTex Citekey: Arikati94MPII94-162

Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show

hide

Title: Research Report / Max-Planck-Institut für Informatik

Source Genre: Series

Creator(s):

Affiliations:

Publ. Info: -

Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -