Abstrakt. I detta papper anser vi att en graf parameter kallas contiguity som syftar till att koda en graf genom en linjär beställning av dess hörn. Vi bevisar att kontinuiteten i cographs är obunden men alltid domineras av O(log n), där n är antalet hörn av grafen. Och vi bevisar att denna gräns är snäv i den meningen att det finns en familj av cographs på n hörnes vars kontiguity är  och (log n). Förutom dessa resultat på det värsta-fall contiguity av cographs, vi utforma en linjär-tid konstant-ratio approximation algoritm för att beräkna kontinuiteten i en godtycklig cograph, vilket utgör vårt huvudsakliga resultat. Som en biprodukt av våra bevis, får vi en min-max teorem, som är värt av intresse i sig själv, som anger likhet mellan rangen av ett träd och den minsta höjden dess stigar partitioner.
Låt oss slutligen för fullständighetens skull nämna att REF gav en algoritm som beräknar en konstant kvot approximation av kontinuiteten i en cograph, liksom en motsvarande kodning, i linjär tid.
Linear-time Constant-ratio Approximation Algorithm and Tight Bounds for the Contiguity of Cographs
{'venue': 'SEVENTH INTERNATIONAL WORKSHOP ON ALGORITHMS AND COMPUTATION', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}