Sammanfattning av denna webbsida: Vi börjar med att erbjuda ett nytt, direkt bevis på ekvivalensen mellan problemet med förekomsten av kärnor i digrafer, KER, och satisfiability av propositionsteorier, SAT, vilket ger linjära minskningar i båda riktningarna. Efter att ha infört några linjära minskningar av inmatningskurvan presenterar vi nya algoritmer för KER, med variationer som utnyttjar lösare av booleska ekvationer. I värsta fall, algoritmer prova alla uppdrag att antingen en feedback vertex uppsättning, $ F$, eller en uppsättning noder $ E$ vidrör endast alla jämna cykler. Därför är KER fast parameter dragbar inte bara i storleken på $ F$, som observerats tidigare, men också i storleken $ E$. En liten ändring av dessa algoritmer leder till en gren och bunden algoritm för KER som är praktiskt taget identisk med DPLL-algoritmen för SAT. Detta tyder på djupare analogier mellan de två områdena och det sannolika scenariot för KER-forskning som står inför de utmaningar som är kända från arbetet med SAT.   1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 17 18 19 20 21 22 23 24 26 27 28 29 31 32 33 34 35 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 61 62 63 64 65 Hitta kärnor eller lösa SAT Micha l Walicki och Sjur Dyrkolbotn Institutionen för informationsteknologi, University of Bergen michal@ii.uib.no Vi börjar med att erbjuda ett nytt, direkt bevis på likvärdigheten mellan problemet med förekomsten av kärnor i digrafer, KER, och satisfiability av propositionsteorier, SAT, vilket ger linjära minskningar i båda riktningarna. Efter att ha infört några linjära minskningar av inmatningskurvan presenterar vi nya algoritmer för KER, med variationer som utnyttjar lösare av booleska ekvationer. I värsta fall, algoritmer prova alla uppdrag att antingen en feedback vertex set, F, eller en uppsättning noder E vidrör endast alla jämna cykler. Därför är KER fast parameter dragbar inte bara i storleken på F, Som observerats tidigare, men också i storleken på E. En liten ändring av dessa algoritmer leder till en gren och bunden algoritm för KER som är praktiskt taget identisk med DPLL algoritm för SAT. Detta tyder på djupare jämförelser mellan de två områdena och det sannolika scenariot för KER-forskning som står inför de utmaningar som är kända i arbetet med SAT.
Samtidigt, enligt REF, är det ett ekvivalensförhållande mellan problemet med förekomsten av kärnor i digrafer och satisfiability av propositionsteorier (SAT).
Finding kernels or solving SAT
{'venue': 'J. Discrete Algorithms', 'journal': 'J. Discrete Algorithms', 'mag_field_of_study': ['Mathematics', 'Computer Science']}