Efficient Algorithms for Geometric Graph Search Problems

DOI10.1137/0215033MaRDI QIDQ3719850zbMATH OpenOpenAlexFDO

Authors T. Asano, Hideki Imai

Publication date 1986

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/854cb8c4e1c75ffef990d3fdacfe8ff0a24e5bc7

zbMATH Keywords

algorithmcomputational geometrydata structuresgraph algorithmsconnectivitymaximum independent setbreadth first searchmaximum matchingbiconnected componentsdepth first searchgeometric intersection graphsegment treeintersection searchlinear-time set unionorthogonal segment

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1302178
• scientific article; zbMATH DE number 437554
• Geometric speed-up techniques for finding shortest paths in large sparse graphs
• Space-efficient algorithms for reachability in directed geometric graphs
• Approximation Algorithms for Geometric Intersection Graphs
• Graph-Theoretic Solutions to Computational Geometry Problems
• Efficient algorithms for geometric partial matching
• Parallel algorithms for geometric graph problems
• Polynomial-time approximation schemes for geometric graphs

Cited in

(28)

• On geometric shape construction via growth operations
• Minimum-link paths revisited
• Approximation algorithms for decomposing octilinear polygons
• An efficient and effective approximation algorithm for the Map Labeling Problem
• On a minimum linear classification problem
• Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane
• A linear-time algorithm for a special case of disjoint set union
• Labeling a rectilinear map more efficiently
• Close-to-optimal algorithm for rectangular decomposition of 3D shapes.
• Minimum-link shortest paths for polygons amidst rectilinear obstacles
• Minimum convex partition of a polygon with holes by cuts in given directions
• A practical map labeling algorithm.
• Minimum k-adjacent rectangles of orthogonal polygons and its application
• Linear time algorithms for graph search and connectivity determination on complement graphs.
• scientific article; zbMATH DE number 4158672 (Why is no real title available?)
• Space-efficient algorithms for reachability in directed geometric graphs
• Minimum k-partitioning of rectilinear polygons
• Morphological decomposition and compression of binary images via a minimum set cover algorithm
• Searching edges in the overlap of two plane graphs
• Minimum dissection of a rectilinear polygon with arbitrary holes into rectangles
• Labeling points with given rectangles
• Quadrilaterizing an Orthogonal Polygon in Parallel
• Schematization of networks
• On geometric shape construction via growth operations
• PARTITIONING 3D PHANTOMS INTO HOMOGENEOUS CUBOIDS
• scientific article; zbMATH DE number 437554 (Why is no real title available?)
• scientific article; zbMATH DE number 177554 (Why is no real title available?)
• Testing bipartiteness of geometric intersection graphs

This page was built for publication: Efficient Algorithms for Geometric Graph Search Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3719850)