Kvasi-tvådelad graf
Inom det matematiska området för grafteorin sägs en instans av Steinerträdsproblemet (som består av en oriktad graf G och en uppsättning R av terminala hörn som måste kopplas till varandra) vara kvasi-bipartit om de icke-terminala hörnen i G bildar en oberoende uppsättning , dvs om varje kant är infallande på minst en terminal. Detta generaliserar konceptet med en tvådelad graf : om G är tvådelad, och R är uppsättningen av hörn på ena sidan av tvådelad graf, är uppsättningen till R automatiskt oberoende.
Detta koncept introducerades av Rajagopalan och Vazirani som använde det för att tillhandahålla en (3/2 + ε) approximationsalgoritm för Steinerträdproblemet i sådana fall. Därefter togs ε-faktorn bort av Rizzi och en 4/3 approximationsalgoritm erhölls av Chakrabarty et al. Samma koncept har använts av efterföljande författare om Steinerträdproblemet, t.ex. Robins och Zelikovsky föreslog en approximationsalgoritm för Steinerträdproblem som på kvasi-tvådelade grafer har ett approximationsförhållande på 1,28. Komplexiteten i Robins och Zelikovskys algoritm är O( m n 2 ) , där m och n är antalet terminaler respektive icke-terminaler i grafen. Vidare har Gröpl et al. gav en 1,217-approximationsalgoritm för det speciella fallet med enhetligt kvasi-bipartita instanser.