Algorithms for interval structures with applications

DOI10.1016/J.TCS.2011.12.075MaRDI QIDQ388095zbMATH OpenOpenAlexFDO

Authors Danny Z. Chen, Ewa Misiołek

Publication date 19 December 2013

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.12.075

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Algorithms for interval structures with applications
• On the \(k\)-coloring of intervals
• An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
• Shortest color-spanning intervals
• Optimal parallel algorithm for shortest-paths problem on interval graphs

Cites work

• scientific article; zbMATH DE number 3706451 (Why is no real title available?)
• scientific article; zbMATH DE number 1875422 (Why is no real title available?)
• A PTAS for TSP with neighborhoods among fat regions in the plane
• A linear-time algorithm for a special case of disjoint set union
• A unified approach to domination problems on interval graphs
• Algorithmic graph theory and perfect graphs
• An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
• An optimal algorithm to solve the all-pair shortest path problem on interval graphs
• An optimal parallel algorithm for the minimum circle-cover problem
• Automata, Languages and Programming
• Chromatic nearest neighbor searching: A query sensitive approach
• Computing minimum diameter color-spanning sets
• Computing toolpaths for 5-axis NC machines
• Design and implementation of an efficient priority queue
• Finding an optimal path without growing the tree
• Finding level-ancestors in trees
• Free-Form Surface Partition in 3-D
• Linear time algorithms on circular-arc graphs
• MINIMUM POLYGON TRANSVERSALS OF LINE SEGMENTS
• NP-Completeness of Spreading Colored Points
• On a circle-cover minimization problem
• On intersecting a set of parallel line segments with a convex polygon of minimum area
• Parallel circle-cover algorithms
• Preserving order in a forest in less than logarithmic time and linear space
• SMALLEST COLOR-SPANNING OBJECT REVISITED
• Solving the all-pair shortest path query problem on interval and circular-arc graphs
• TSP with neighborhoods of varying size

Cited in

(8)

• Computing largest minimum color-spanning intervals of imprecise points
• Color spanning objects: algorithms and hardness results
• Minimum width color spanning annulus
• Minimum width color spanning annulus
• Algorithms for interval structures with applications
• Color spanning objects: algorithms and hardness results
• Shortest color-spanning intervals
• Color-spanning localized query

This page was built for publication: Algorithms for interval structures with applications

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