Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/101335
| Title: | Modification problems toward proper (helly) circular-arc graphs | Authors: | Cao, Y Yuan, H Wang, J |
Issue Date: | 2023 | Source: | In J Leroux, S Lombardy, & D Peleg (Eds.), 48th International Symposium on Mathematical Foundations of Computer Science : MFCS 2023, August 28 to September 1, 2023, Bordeaux, France, p. 31:1-31:14. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. | 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. | Keywords: | proper (Helly) circular-arc graph Graph modification problem |
Publisher: | Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing | ISBN: | 978-3-95977-292-1 | DOI: | 10.4230/LIPIcs.MFCS.2023.31 | Rights: | © Yixin Cao, Hanchun Yuan, and Jianxin Wang; licensed under Creative Commons License CC-BY 4.0 (https://creativecommons.org/licenses/by/4.0/) The following publication Cao, Y., Yuan, H., & Wang, J. (2023). Modification Problems Toward Proper (Helly) Circular-Arc Graphs. In J. Leroux, S. Lombardy, & D. Peleg (Eds.), 48th International Symposium on Mathematical Foundations of Computer Science : MFCS 2023, August 28 to September 1, 2023, Bordeaux, France (pp. 31:1-31:14). Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing is available at https://doi.org/10.4230/LIPIcs.MFCS.2023.31. |
| Appears in Collections: | Conference Paper |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Cao_Modification_Problems_Proper.pdf | 717.75 kB | Adobe PDF | View/Open |
Access
View full-text via PolyU eLinks 
Page views
154
Last Week
6
6
Last month
Citations as of Nov 9, 2025
Downloads
70
Citations as of Nov 9, 2025
SCOPUSTM
Citations
1
Citations as of Jun 21, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.