Блог пользователя never_giveup

Автор never_giveup, история, 3 года назад, По-английски

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!

  • Проголосовать: нравится
  • +51
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +51 Проголосовать: не нравится