BROWSE

Related Scientist

's photo.

수리 및 계산 과학 연구단
more info

ITEM VIEW & DOWNLOAD

Towards Constant-Factor Approximation for Chordal/Distance-Hereditary Vertex Deletion

Cited 0 time in webofscience Cited 0 time in scopus
65 Viewed 0 Downloaded
Title
Towards Constant-Factor Approximation for Chordal/Distance-Hereditary Vertex Deletion
Author(s)
Jungho Ahn; Kim, E.J.; Lee, E.
Publication Date
2022-07
Journal
Algorithmica, v.84, no.7, pp.2106 - 2133
Publisher
Springer Verlag
Abstract
under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.For a family of graphs F, WeightedF-Deletion is the problem for which the input is a vertex weighted graph G= (V, E) and the goal is to delete S⊆ V with minimum weight such that G\ S∈ F. Designing a constant-factor approximation algorithm for large subclasses of perfect graphs has been an interesting research direction. Block graphs, 3-leaf power graphs, and interval graphs are known to admit constant-factor approximation algorithms, but the question is open for chordal graphs and distance-hereditary graphs. In this paper, we add one more class to this list by presenting a constant-factor approximation algorithm when F is the intersection of chordal graphs and distance-hereditary graphs. They are known as ptolemaic graphs and form a superset of both block graphs and 3-leaf power graphs above. Our proof presents new properties and algorithmic results on inter-clique digraphs as well as an approximation algorithm for a variant of Feedback Vertex Set that exploits this relationship (named Feedback Vertex Set with Precedence Constraints), each of which may be of independent interest.
URI
https://pr.ibs.re.kr/handle/8788114/12389
DOI
10.1007/s00453-022-00963-7
ISSN
0178-4617
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > 1. Journal Papers (저널논문)
Files in This Item:
There are no files associated with this item.

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse