Journal
ALGORITHMS AND DISCRETE APPLIED MATHEMATICS, CALDAM 2023
Volume 13947, Issue -, Pages 377-388Publisher
SPRINGER INTERNATIONAL PUBLISHING AG
DOI: 10.1007/978-3-031-25211-2_29
Keywords
Matching; Acyclic matching; Minimum maximal acyclic matching; Linear-time algorithm
Ask authors/readers for more resources
This paper investigates the problem of MIN-MAX-ACY-Matching and presents a linear-time algorithm to solve it in proper interval graphs.
Given a graph G, MIN-MAX-ACY-MATCHING is the problem of finding a maximal matching M in G of minimum cardinality such that the set of M-saturated vertices induces an acyclic subgraph in G. The decision version of MIN-MAX-ACY-MATCHING is known to be NP-complete even for planar perfect elimination bipartite graphs. In this paper, we give the first positive algorithmic result for MIN-MAX-ACY-Matching by presenting a linear-time algorithm for computing a minimum cardinality maximal acyclic matching in proper interval graphs.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
