33 citations · 116 across the 28 of their papers we have counts for
Showing 2017 · cs.DSShow all
2 papers · 2 filters
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…