A dynamic programming algorithm for the maximum induced matching problem in permutation graphs

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 9
  • Download : 0
For a finite undirected graph G = (V, E) and a positive integer k >= 1, an edge set M subset of E is a distance-k matching if the pairwise distance of edges in M is at least k in G. The special case k = 2 has been studied under the name maximum induced matching (MIM for short), i.e., a maximum matching which forms an induced subgraph in G. MIM arises in many applications, such as artificial intelligence, game theory, computer networks, VLSI design and marriage problems. In this paper, we design an O(n(2)) solution for finding MIM in permutation graphs based on a dynamic programming method on edges with the aid of the sweep line technique. Our result is better than the best known algorithm.
Publisher
ASSOC COMPUTING MACHINERY
Issue Date
2018-12
Language
English
Citation

9th International Symposium on Information and Communication Technology (SoICT), pp.92 - 97

DOI
10.1145/3287921.3287961
URI
http://hdl.handle.net/10203/274992
Appears in Collection
RIMS Conference Papers
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0