Nyligen utfört arbete av Elmasry et al. (STACS 2015) och Asano m.fl. (ISAAC 2014) omprövade klassiska grundläggande grafalgoritmer med fokus på att förbättra rymdens komplexitet. Elmasry m.fl. gav bland annat en implementation av djup första sökning (DFS) av en graf på n hörn och m kanter, tar O(m lg lg n) tid 1 med hjälp av O(n) bitar av utrymme förbättras på tidslinjen för O (m lg n) på grund av Asano et al. Därefter Banerjee et al. (COCOON 2016) gav en O(m + n) tid implementation med hjälp av O(m + n) bitar, för DFS och dess klassiska applikationer (inklusive testning för bikonnektivitet, och hitta skär hörn och skärkanter). Nyligen, Kammer et al. (MCS 2016) gav en algoritm för att testa bikonnektivitet med hjälp av O(n + min{m, n lg lg n}) bitar i linjär tid. I detta dokument behandlar vi O(n) bits implementeringar av de klassiska applikationerna av DFS. Dessa inkluderar problemet med att hitta skär hörn, och bianslutna komponenter, kedjedekomposition och st-numrering. Klassiska algoritmer för dem använder vanligtvis DFS och vissa  på varje nod (lg n) bitar av information. Våra O(n)-bit implementeringar för dessa problem tar O(m lg c n lg lg n) tid för några små konstant c (c ≤ 3). Centralt för vårt genomförande är en kortfattad representation av DFS-trädet och en utrymmeseffektiv uppdelning av DFS-trädet i anslutna delträd, vilket kanske är av oberoende intresse för att utforma utrymmeseffektiva grafalgoritmer.  ACM Subject Classification Motiverad av den snabba tillväxten av enorma datamängder ("stora data"), blir rymdeffektiva algoritmer allt viktigare än någonsin tidigare. Spridningen av handhållna eller inbyggda enheter som är utrustade med endast en liten mängd allmänt minne ger en annan motivation för att studera rymdeffektiva algoritmer. I vissa av dessa enheter, skriva i minnet är en kostsam operation i termer av både hastighet och tid än läsning. I sådana scenarier är algoritmer som inte ändrar inmatningen och använder endast en begränsad mängd arbetsutrymme mycket önskvärt. Standardmodellen för att studera rymdeffektiva algoritmer är den läsbara minnesmodellen, och det finns en rik historia i beräkningskomplex teori av sådana algoritmer som använder 1 Vi använder lg för att beteckna logaritm till basen 2.
Rymdgränser för formen O(n log(m/n)) för samma problem nämndes av Chakraborty et al. Hoppa över det.
Biconnectivity, chain decomposition and $st$-numbering using $O(n)$ bits
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}