Vi studerar problemet med att bestämma omkretsen av en oviktad oriktad graf. Vi får flera nya effektiva approximationsalgoritmer för grafer med n noder och m kanter och okänd omkrets g. Vi anser additiva och multiplikativa approximationer. Tillsatsens tillämpningsområde Vi presenterar: • en Õ (n 3 /m)-tid algoritm som returnerar en cykel av längd som mest g + 2 om g är jämn och g + 3 om g är udda. Detta kompletterar det seminala arbetet av Itai och Rodeh [SIAM J. Computing'78] som gav en algoritm som i O(n 2 ) tid finner en cykel av längd g om g är jämn, och g + 1 om g är udda. • anÕ(n 3 /m)-tid algoritm som returnerar en cykel av längd som mest g ′ + 2, där g ′ är längden på den kortaste jämn cykel i G. Detta resultat kompletterar arbetet av Yuster och Zwick [SIAM J. Discrete Math'97] som visade hur man beräknar g ′ i O(n 2 ) tid. Multiplikativa approximationer. Vi presenterar: • anÕ(n 5/3 )-tidsalgoritm som returnerar en cykel av längd högst 3g/2 + z/2 när g är jämn och 3g/2 + z/2 + 1 när g är udda, där z = -g mod 4, z  till {0, 1, 2, 3}. Detta ger en Õ(n 5/3 )-tid 2- approximation för omkretsen, den första subquadratiska 2- approximation algoritm, lösa en öppen fråga om Lingas och Lundell [IPL'09]. • en O(n 1.968 )-tid (8/5)-tillnärmningsalgoritm för omkretsen i grafer med omkrets minst 4 (dvs. triangelfria grafer). Detta är den första subquadratiska tiden (2 − ε) - approximation algoritm för omkretsen för triangelfria grafer, för alla ε > 0. Vi bevisar att en deterministisk algoritm av detta slag inte är möjlig för riktade grafer, vilket visar en stark separation mellan oriktade och riktade grafer för omkrets approximation.
Roditty och Vassilevska W. REF presenterade en O(n 5/3 )-tid deterministisk multiplikativ 2- approximationsalgoritm.
Subquadratic time approximation algorithms for the girth
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}