Modification problems toward proper (Helly) circular-arc graphs

Yixin Cao; Hanchun Yuan; Jianxin Wang

doi:10.1016/j.ic.2024.105211

Modification problems toward proper (Helly) circular-arc graphs

Yixin Cao, Hanchun Yuan, Jianxin Wang

The Hong Kong Polytechnic University

Research output: Journal article publication › Journal article › Academic research › peer-review

1 Citation (Scopus)

Abstract

We present a 9^k⋅n^O(1)-time algorithm for the proper circular-arc vertex deletion problem, resolving an open problem of van 't Hof and Villanger [Algorithmica 2013] and Crespelle et al. [Computer Science Review 2023]. Our structural study also implies parameterized algorithms for modification problems toward proper Helly circular-arc graphs.

Original language	English
Article number	105211
Journal	Information and Computation
Volume	301
DOIs	https://doi.org/10.1016/j.ic.2024.105211
Publication status	Published - Dec 2024

ASJC Scopus subject areas

Theoretical Computer Science
Information Systems
Computer Science Applications
Computational Theory and Mathematics

More information

10.1016/j.ic.2024.105211

Cite this

@article{1efcdaa317a54c569d44ec82a2f8d363,

title = "Modification problems toward proper (Helly) circular-arc graphs",

abstract = "We present a 9k⋅nO(1)-time algorithm for the proper circular-arc vertex deletion problem, resolving an open problem of van 't Hof and Villanger [Algorithmica 2013] and Crespelle et al. [Computer Science Review 2023]. Our structural study also implies parameterized algorithms for modification problems toward proper Helly circular-arc graphs.",

author = "Yixin Cao and Hanchun Yuan and Jianxin Wang",

note = "Publisher Copyright: {\textcopyright} 2024 Elsevier Inc.",

year = "2024",

month = dec,

doi = "10.1016/j.ic.2024.105211",

language = "English",

volume = "301",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - Modification problems toward proper (Helly) circular-arc graphs

AU - Cao, Yixin

AU - Yuan, Hanchun

AU - Wang, Jianxin

PY - 2024/12

Y1 - 2024/12

N2 - We present a 9k⋅nO(1)-time algorithm for the proper circular-arc vertex deletion problem, resolving an open problem of van 't Hof and Villanger [Algorithmica 2013] and Crespelle et al. [Computer Science Review 2023]. Our structural study also implies parameterized algorithms for modification problems toward proper Helly circular-arc graphs.

AB - We present a 9k⋅nO(1)-time algorithm for the proper circular-arc vertex deletion problem, resolving an open problem of van 't Hof and Villanger [Algorithmica 2013] and Crespelle et al. [Computer Science Review 2023]. Our structural study also implies parameterized algorithms for modification problems toward proper Helly circular-arc graphs.

UR - https://www.scopus.com/pages/publications/85200999920

U2 - 10.1016/j.ic.2024.105211

DO - 10.1016/j.ic.2024.105211

M3 - Journal article

AN - SCOPUS:85200999920

SN - 0890-5401

VL - 301

JO - Information and Computation

JF - Information and Computation

M1 - 105211

ER -

Modification problems toward proper (Helly) circular-arc graphs

Abstract

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this