No, I don't think laminar matroids are a subset of graphic matroids (nor vice versa).
I think laminar matroids occur fairly naturally in lots of places where a computer scientist would use a heap.
> Hierarchical or Nested Constraints:
> When problems involve hierarchical resource constraints—say, scheduling with nested deadlines or quotas that are imposed at different levels—a laminar family naturally describes these relationships. The corresponding laminar matroid models the “at most so many” restrictions on various overlapping (but nested) groups.
> Network Design and Resource Allocation:
> In network design or resource allocation, you may encounter situations where resources are grouped in a hierarchy (for example, a network might have capacities on various subnetworks that nest within one another). Laminar matroids capture this kind of structure.
One of my original motivating examples was something like this: suppose you have a compiler that's supposed to give good error messages. Now it gets input with mismatched parens like "a = (b * (c + d);"
Both "a = (b * c + d);" and "a = b * (c + d);" are ways to remove the fewest number of characters to get a well-balanced expression. Assume some other parts of your parser give you some weights to tell you which parens are less suspicious / more likely to be intended by the user. You want to select the subsequence of characters that has the highest total weight, or equivalently: delete the most suspicous parens only.
In any real world scenario, you would just use a normal heap to do this in O(n log n) time. But I was investigating whether we could do it in linear time, or prove that linear time ain't possible.
Well, I figured out that linear time is possible.
I'm actually working on writing it down and publishing it as a paper or at least blog post.
I think laminar matroids occur fairly naturally in lots of places where a computer scientist would use a heap.
> Hierarchical or Nested Constraints:
> When problems involve hierarchical resource constraints—say, scheduling with nested deadlines or quotas that are imposed at different levels—a laminar family naturally describes these relationships. The corresponding laminar matroid models the “at most so many” restrictions on various overlapping (but nested) groups.
> Network Design and Resource Allocation:
> In network design or resource allocation, you may encounter situations where resources are grouped in a hierarchy (for example, a network might have capacities on various subnetworks that nest within one another). Laminar matroids capture this kind of structure.
One of my original motivating examples was something like this: suppose you have a compiler that's supposed to give good error messages. Now it gets input with mismatched parens like "a = (b * (c + d);"
Both "a = (b * c + d);" and "a = b * (c + d);" are ways to remove the fewest number of characters to get a well-balanced expression. Assume some other parts of your parser give you some weights to tell you which parens are less suspicious / more likely to be intended by the user. You want to select the subsequence of characters that has the highest total weight, or equivalently: delete the most suspicous parens only.
In any real world scenario, you would just use a normal heap to do this in O(n log n) time. But I was investigating whether we could do it in linear time, or prove that linear time ain't possible.
Well, I figured out that linear time is possible.
I'm actually working on writing it down and publishing it as a paper or at least blog post.