Abstrakt. Med tanke på ett par av grafen G1 = (V, E1), G2 = (V, E2) på samma vertex uppsättning, en uppsättning S  på V är en maximal gemensam ansluten uppsättning av G1 och G2 om subgraferna av G1 och G2 inducerade av S är båda anslutna och S är maximal inkluderingsordning. Maximala gemensamma anslutna uppsättningar Problem (CCP för kort) består i att identifiera partitionen av V i maximal gemensamma anslutna uppsättningar av G1 och G2. Detta problem har många praktiska tillämpningar, särskilt inom beräkningsbiologin. Låt n =... och m =............ +.......... Vi presenterar en O(n + m) log n) värsta fall tid algoritm lösa CCP när G1 och G2 är två intervall grafer. Algoritmen kombinerar maximal clique path decompositions av de två indatagraferna tillsammans med en Hopcroft-liknande partitioneringsmetod.
Precis som i det föregående arbetet minskar den föreslagna algoritmen komplexiteten till O(n + m) log n) REF.
Maximal Common Connected Sets of Interval Graphs
{'venue': 'CPM', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}