7 citations · 7 across the 9 of their papers we have counts for
Showing 2017Show all
2 papers · 1 filter
cs.DS2017
Maximum Induced Matching Algorithms via Vertex Ordering Characterizations
Michel Habib, Lalla Mouatadid
We study the maximum induced matching problem on a graph g. Induced matchings correspond to independent sets in L2(g), the square of the line graph of g. The problem is NP-complete…
cs.DS2017
A New Graph Parameter To Measure Linearity
Pierre Charbit, Michel Habib, Lalla Mouatadid +1
Consider a sequence of LexBFS vertex orderings σ1, σ2, . . . where each ordering σi is used to break ties for σi+1. Since the total number of vertex orderings of a finite graph is…