DC Field | Value | Language |
---|---|---|
dc.contributor.author | Viet-Dung Nguyen | ko |
dc.contributor.author | Ba-Thai Pham | ko |
dc.contributor.author | Viet-Hung Tran | ko |
dc.contributor.author | Phan-Thuan Do | ko |
dc.date.accessioned | 2020-06-29T07:21:03Z | - |
dc.date.available | 2020-06-29T07:21:03Z | - |
dc.date.created | 2020-06-17 | - |
dc.date.issued | 2018-12 | - |
dc.identifier.citation | 9th International Symposium on Information and Communication Technology (SoICT), pp.92 - 97 | - |
dc.identifier.uri | http://hdl.handle.net/10203/274992 | - |
dc.description.abstract | 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. | - |
dc.language | English | - |
dc.publisher | ASSOC COMPUTING MACHINERY | - |
dc.title | A dynamic programming algorithm for the maximum induced matching problem in permutation graphs | - |
dc.type | Conference | - |
dc.identifier.wosid | 000457832900013 | - |
dc.identifier.scopusid | 2-s2.0-85059963758 | - |
dc.type.rims | CONF | - |
dc.citation.beginningpage | 92 | - |
dc.citation.endingpage | 97 | - |
dc.citation.publicationname | 9th International Symposium on Information and Communication Technology (SoICT) | - |
dc.identifier.conferencecountry | US | - |
dc.identifier.conferencelocation | Da Nang, VIETNAM | - |
dc.identifier.doi | 10.1145/3287921.3287961 | - |
dc.contributor.nonIdAuthor | Ba-Thai Pham | - |
dc.contributor.nonIdAuthor | Viet-Hung Tran | - |
dc.contributor.nonIdAuthor | Phan-Thuan Do | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.