A certifying and dynamic algorithm for the recognition of proper circular-arc graphs | ||
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación | |
| dc.contributor.author | Soulignac, Francisco Juan | |
| dc.date.issued | 2021-10 | |
| dc.description.abstract | We present a dynamic algorithm for the recognition of proper circular-arc (PCA) graphs, that supports the insertion and removal of vertices (together with its incident edges). The main feature of the algorithm is that it outputs a minimally non-PCA induced subgraph when the insertion of a vertex fails. Each operation cost O(logn+d) time, where n is the number vertices and d is the degree of the modified vertex. When removals are disallowed, each insertion is processed in O(d) time. The algorithm also provides two constant-time operations to query if the dynamic graph is proper Helly (PHCA) or proper interval (PIG). When the dynamic graph is not PHCA (resp. PIG), a minimally non-PHCA (resp. non-PIG) induced subgraph is obtained. | es |
| dc.description.fil | Fil: Soulignac, Francisco Juan. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación; Argentina | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Soulignac, Francisco Juan; A certifying and dynamic algorithm for the recognition of proper circular-arc graphs; Elsevier Science; Theoretical Computer Science; 889; 10-2021; 105-134 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0304-3975 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/173301 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.pagination | 105-134 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Theoretical Computer Science | es |
| dc.journal.volume | 889 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier Science | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.tcs.2021.07.040 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://arxiv.org/abs/1509.05828 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | * |
| dc.subject | CERTIFYING ALGORITHM | es |
| dc.subject | DYNAMIC REPRESENTATION | es |
| dc.subject | PROPER CIRCULAR-ARC GRAPHS | es |
| dc.subject | PROPER HELLY CIRCULAR-ARC GRAPHS | es |
| dc.subject | PROPER INTERVAL GRAPH | es |
| dc.subject.classification | Ciencias de la Computación | es |
| dc.subject.classification | Ciencias de la Computación e Información | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | A certifying and dynamic algorithm for the recognition of proper circular-arc graphs | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.1e2f299a-f1ea-4d88-bc3e-835f1ed82bcf_B.pdf
- Tamaño:
- 1.26 MB
- Formato:
- Adobe Portable Document Format