Chandoo, Maurice: Deciding circular-arc graph isomorphism in parameterized logspace. In: Leibniz International Proceedings in Informatics, LIPIcs 47 (2016), 26. DOI: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.26
Zusammenfassung: | |
We compute a canonical circular-arc representation for a given circular-arc (CA) graph which implies solving the isomorphism and recognition problem for this class. To accomplish this we split the class of CA graphs into uniform and non-uniform ones and employ a generalized version of the argument given by Köbler et al. (2013) that has been used to show that the subclass of Helly CA graphs can be canonized in logspace. For uniform CA graphs our approach works in logspace and in addition to that Helly CA graphs are a strict subset of uniform CA graphs. Thus our result is a generalization of the canonization result for Helly CA graphs. In the non-uniform case a specific set Omega of ambiguous vertices arises. By choosing the parameter k to be the cardinality of Omega this obstacle can be solved by brute force. This leads to an O(k + log(n)) space algorithm to compute a canonical representation for non-uniform and therefore all CA graphs. | |
Lizenzbestimmungen: | CC BY 3.0 Unported |
Publikationstyp: | Article |
Publikationsstatus: | publishedVersion |
Erstveröffentlichung: | 2016 |
Die Publikation erscheint in Sammlung(en): | Fakultät für Elektrotechnik und Informatik |
Pos. | Land | Downloads | ||
---|---|---|---|---|
Anzahl | Proz. | |||
1 | Germany | 84 | 66,67% | |
2 | United States | 21 | 16,67% | |
3 | China | 8 | 6,35% | |
4 | France | 2 | 1,59% | |
5 | Canada | 2 | 1,59% | |
6 | Zimbabwe | 1 | 0,79% | |
7 | No geo information available | 1 | 0,79% | |
8 | Ukraine | 1 | 0,79% | |
9 | Taiwan | 1 | 0,79% | |
10 | Singapore | 1 | 0,79% | |
andere | 4 | 3,17% |
Hinweis
Zur Erhebung der Downloadstatistiken kommen entsprechend dem „COUNTER Code of Practice for e-Resources“ international anerkannte Regeln und Normen zur Anwendung. COUNTER ist eine internationale Non-Profit-Organisation, in der Bibliotheksverbände, Datenbankanbieter und Verlage gemeinsam an Standards zur Erhebung, Speicherung und Verarbeitung von Nutzungsdaten elektronischer Ressourcen arbeiten, welche so Objektivität und Vergleichbarkeit gewährleisten sollen. Es werden hierbei ausschließlich Zugriffe auf die entsprechenden Volltexte ausgewertet, keine Aufrufe der Website an sich.