7 citations · 7 across the 9 of their papers we have counts for
Showing cs.DSShow all
3 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…
cs.DS2014★ 7 cited
Linear Time LexDFS on Cocomparability Graphs
Ekkehard Köhler, Lalla Mouatadid
Lexicographic depth first search (LexDFS) is a graph search protocol which has already proved to be a powerful tool on cocomparability graphs. Cocomparability graphs have been well…