Abstrakt. 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 implementationer av bredd första sökning (BFS) och djup första sökning (DFS) i en graf på n hörn och m kanter, tar O(m + n) tid med hjälp av O(n) och O (n lg lg n) bitar av utrymme respektive förbättra den naiva O(n lg n) 1 bits genomförande. Vi fortsätter detta arbete med fokus på rymden. Vårt första resultat är en enkel datastruktur som kan underhålla alla undergrupper av S i ett universum av n element med n + o(n) bitar och stöd i konstant tid, bortsett från standardinmatningen, ta bort och medlemskap frågor, operationen hitta någon som hittar och returnerar någon del av uppsättningen (eller utgångar som uppsättningen är tom). Med hjälp av detta ger vi en BFS-implementation som tar O(m + n) tid att använda högst 2n + o(n) bitar. Senare förbättrar vi ytterligare utrymmeskravet för BFS till högst 1.585n+o(n) bitar om än med en liten ökning av körtiden till O(m lg nf (n)) tid där f (n) är någon extremt långsam växande funktion av n. Dessa förbättrar utrymmet med en konstant faktor från tidigare representationer. Vi visar användningen av vår datastruktur genom att utveckla en annan datastruktur med hjälp av den som kan representera en sekvens av n icke-negativa heltal x1, x2,. ... xn använder högst xi + n) bitar och, i konstant tid, avgöra om i-th elementet är 0 eller minska det på annat sätt. Vi använder denna datastruktur för att mata ut hörnen på en • riktad acyklisk graf i topologisk sorterad ordning i O(m + n) tid och O(m + n) bitar, och • graf med degeneracy d i degeneracy ordning i O(nd) tid med hjälp av O(nd) bitar. Vi diskuterar också en algoritm för att hitta en minsta vikt spanning träd av en viktad oriktad graf med hjälp av som mest n + o(n) bitar. För DFS har vi två typer av resultat. Specifikt, • vi tillhandahåller en implementation för DFS som tar O (m + n) tid med hjälp av O (m + n) bitar. Detta svarar åtminstone för glesa grafer, en fråga i [3] som ställde om DFS kan utföras i O(m+n) tid och O(n) bitar. Med hjälp av DFS algoritm och andra försiktiga En preliminär version av detta dokument visas i förhandlingarna i COCOON 2016. 1 Vi använder lg för att beteckna logaritm till basen 2. implementationer, kan vi bestämma skär hörn, broar och maximal 2-anslutna komponenter bland annat, i O(m + n) tid och O(m + n) bitar; tidigare linjära tid algoritmer för dessa problem som används  och (n lg n) bitar av utrymme. Dessa rymdeffektiva implementationer erhålls med hjälp av ett utrymme effektivt genomförande av kedjenedbrytning och en unary kodning av graderna av grafens hörn, och några koncisa datastrukturer. • Vi presenterar utrymme effektiva implementationer för att hitta starkt anslutna komponenter i en riktad graf, för att mata ut hörnen i en riktad acyklisk graf på ett topologiskt sorterat sätt, och för att hitta en gles biansluten subgraf av en biansluten graf med hjälp av O(n) bitar. Dessa förbättrar det utrymme som krävs för tidigare genomföranden från  och (n lg n) bitar.
Olika gränser för dessa problem hävdades utan bevis av Banerjee, Chakraborty och Raman REF: O(m log n log log n) tid med O(n) bitar för SCC-problemet och O(n + m) tid med m + 3n + o(n + m) bitar samt O(m log n) tid med O(n) bitar för topologisk sortering.
Improved Space efficient algorithms for BFS, DFS and applications
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}