Efficient Algorithms for Geometric Graph Search Problems
From MaRDI portal
Publication:3719850
DOI10.1137/0215033zbMath0591.68068OpenAlexW1976676339MaRDI QIDQ3719850
Publication date: 1986
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/854cb8c4e1c75ffef990d3fdacfe8ff0a24e5bc7
algorithmconnectivitydata structuresmaximum matchinggraph algorithmscomputational geometrymaximum independent setbreadth first searchbiconnected componentsdepth first searchsegment treegeometric intersection graphintersection searchlinear-time set unionorthogonal segment
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Minimum-link shortest paths for polygons amidst rectilinear obstacles, Labeling a rectilinear map more efficiently, Minimum K-Adjacent Rectangles of Orthogonal Polygons and its Application, Approximation algorithms for decomposing octilinear polygons, An efficient and effective approximation algorithm for the Map Labeling Problem, On geometric shape construction via growth operations, On geometric shape construction via growth operations, Minimum k-partitioning of rectilinear polygons, Morphological decomposition and compression of binary images via a minimum set cover algorithm, Minimum-link paths revisited, PARTITIONING 3D PHANTOMS INTO HOMOGENEOUS CUBOIDS, Quadrilaterizing an Orthogonal Polygon in Parallel, Minimum dissection of a rectilinear polygon with arbitrary holes into rectangles, An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains, A practical map labeling algorithm., Schematization of networks, On a minimum linear classification problem, Close-to-optimal algorithm for rectangular decomposition of 3D shapes, Labeling points with given rectangles, Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane, Linear time algorithms for graph search and connectivity determination on complement graphs., A linear-time algorithm for a special case of disjoint set union
