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.
I REF presenterade Roditty och Vassilevska Williams den första deterministiska approximationsalgoritmen för omkretsen av oviktade grafer.
Subquadratic time approximation algorithms for the girth
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}