Låt G vara en riktad graf. Ett 2-riktat block i G är en maximal vertex-uppsättning C 2d  på V med  på 2d ≥ 2 sådana att för varje par av distinkta vertex x, y  på C 2d, det finns två vertex-avskiljbara stigar från x till y och två vertex-avskiljande stigar från y till x i G. I motsats till de 2-vertex-anslutna komponenterna i G, kan de subgrafer som induceras av 2-riktade block bestå av få eller inga kanter. I detta dokument presenterar vi två algoritmer för beräkning av de 2-riktade blocken av G i O(min{m, (t sap +t sb )n}n) tid, där t sap är antalet av de starka artikulationspunkterna i G och t sb är antalet av de starka broarna i G. Dessutom studerar vi två relaterade begrepp: 2-starka block och 2-kantiga block av G. Vi ger två algoritmer för beräkning av 2-starka block av G i O(min{m, t sap n}n) tid och vi visar att 2-kantiga block av G kan beräknas i O(min{m, t sb n}n) tid. I detta papper studerar vi också några optimeringsproblem relaterade till de starka artikulationspunkterna och 2-blocken i en riktad graf. Med tanke på en starkt ansluten graf G = (V, E), hitta en minsta kardinalitet som E *. E sådan att G * = (V, E * ) är starkt ansluten och den starka artikulation punkter G sammanfaller med den starka artikulation punkter G *. Detta problem kallas minimum starkt ansluten spännvidd subgraph med samma starka ledpunkter. Vi visar att det finns en linjär tid 17/3 approximation algoritm för detta NPhard problem. Vi anser också att problemet med att hitta en minsta starkt ansluten spännvidd subgraf med samma 2-block i en starkt ansluten graf G. Vi presenterar approximationsalgoritmer för tre versioner av detta problem, beroende på typ av 2-block.
Jaberi Ref övervägde olika optimeringsproblem relaterade till 2EC-B och föreslog motsvarande approximationsalgoritmer.
Computing the $2$-blocks of directed graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}