Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/108641
DC Field | Value | Language |
---|---|---|
dc.contributor | Department of Computing | en_US |
dc.creator | Antony, D | en_US |
dc.creator | Cao, Y | en_US |
dc.creator | Pal, S | en_US |
dc.creator | Sandeep, RB | en_US |
dc.date.accessioned | 2024-08-27T01:21:14Z | - |
dc.date.available | 2024-08-27T01:21:14Z | - |
dc.identifier.uri | http://hdl.handle.net/10397/108641 | - |
dc.language.iso | en | en_US |
dc.publisher | Schloss Dagstuhl – Leibniz-Zentrum für Informatik | en_US |
dc.rights | © Dhanyamol Antony, Yixin Cao, Sagartanu Pal, and R. B. Sandeep; licensed under Creative Commons License CC-BY 4.0 (https://creativecommons.org/licenses/by/4.0/legalcode) | en_US |
dc.rights | The following publication Dhanyamol Antony, Yixin Cao, Sagartanu Pal, and R. B. Sandeep. Switching Classes: Characterization and Computation. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024) is available at https://doi.org/10.4230/LIPIcs.MFCS.2024.11. | en_US |
dc.subject | Graph modification | en_US |
dc.subject | Hereditary graph class | en_US |
dc.subject | Minor-closed graph class | en_US |
dc.subject | Switching | en_US |
dc.title | Switching classes : characterization and computation | en_US |
dc.type | Conference Paper | en_US |
dc.identifier.spage | 11:1 | en_US |
dc.identifier.epage | 11:15 | en_US |
dc.identifier.doi | 10.4230/LIPIcs.MFCS.2024.11 | en_US |
dcterms.abstract | In a graph, the switching operation reverses adjacencies between a subset of vertices and the others. For a hereditary graph class 𝒢, we are concerned with the maximum subclass and the minimum superclass of 𝒢 that are closed under switching. We characterize the maximum subclass for many important classes 𝒢, and prove that it is finite when 𝒢 is minor-closed and omits at least one graph. For several graph classes, we develop polynomial-time algorithms to recognize the minimum superclass. We also show that the recognition of the superclass is NP-hard for H-free graphs when H is a sufficiently long path or cycle, and it cannot be solved in subexponential time assuming the Exponential Time Hypothesis. | en_US |
dcterms.accessRights | open access | en_US |
dcterms.bibliographicCitation | 49th International Symposium on Mathematical Foundations of Computer Science : MFCS 2024, August 26-30, 2024, Bratislava, Slovakia, p. 11:1 - 11:15 | en_US |
dcterms.issued | 2024 | - |
dc.relation.conference | International Symposium on Mathematical Foundations of Computer Science [MFCS] | en_US |
dc.description.validate | 202408 bcch | en_US |
dc.description.oa | Version of Record | en_US |
dc.identifier.FolderNumber | a3147 | - |
dc.identifier.SubFormID | 49691 | - |
dc.description.fundingSource | RGC | en_US |
dc.description.fundingSource | Others | en_US |
dc.description.fundingText | National Natural Science Foundation of China | en_US |
dc.description.pubStatus | Published | en_US |
dc.description.oaCategory | CC | en_US |
Appears in Collections: | Conference Paper |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
LIPIcs.MFCS.2024.11.pdf | 718.74 kB | Adobe PDF | View/Open |
Page views
25
Citations as of Sep 22, 2024
Downloads
11
Citations as of Sep 22, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.