On-line updating of solutions to a class of matroid intersection problems

DOI10.1016/0890-5401(87)90027-7zbMath0621.68044OpenAlexW1968928800MaRDI QIDQ1090461

Greg N. Frederickson, Mandayam A. Srinivas

Publication date: 1987

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(87)90027-7

zbMATH Keywords

planar graphData structurespartition matroidred-green job schedulered-green minimum spanning treeupdate algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items (1)

Efficient solution of the matroid product problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matroid optimization with the interleaving of two ordered sets
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Maintenance of configurations in the plane
• Scheduling of unit-length independent tasks with execution constraints
• A data structure for dynamic trees
• Efficient algorithms for a family of matroid intersection problems
• New Data Structures for Orthogonal Range Queries
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Adding range restriction capability to dynamic data structures
• Finding Minimum Spanning Trees
• Maximum matching in a convex bipartite graph

This page was built for publication: On-line updating of solutions to a class of matroid intersection problems