never_giveup's blog

By never_giveup, history, 3 years ago, In English

I'm trying to find some article or at least a name of some type of bipartite graph, description follows.

  • Left part contains exactly $$$n$$$ nodes, numbered $$$1$$$ through $$$n$$$.

  • Right part contains $$$m$$$ nodes, each node is associated with a segment $$$[l; r]$$$, where $$$1 \le l \le r \le n$$$.

  • There is an edge $$$(i, j)$$$ iff $$$l_j \le i \le r_j$$$.

It seems natural to call such graph as a bipartite line graph, but there is another (apparently more popular) graph called line graph, which has nothing to do with mine.

One thing to mention is that this graph is considered by me in terms of flows, so probably it is considered in such context in science too.

If someone knows it's name, or even saw an article mentioning it, I would be very grateful to that person for sharing this information!

  • Vote: I like it
  • +51
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +51 Vote: I do not like it