A hipergráfok és az alacsony egyidejűségű Euler-diagramok minimális fa támogatása

  • Boris Klemz
  • Tamara Mchedlidze
  • Martin Nöllenburg

Absztrakt

Ebben a cikkben bemutatunk egy O (n 2 (m + log n)) - idő algoritmust a H = (V, S) hipergráf n csúcsú és m hiperélű minimális súlyú fa támogatásának (ha van ilyen) kiszámításához. Ez javítja a korábban legismertebb algoritmust O futási idővel (n 4 m 2). H alátámasztása a G grafikonja V-n, így az S minden egyes hiperpontja összekapcsolt részgráfot indukál G-ben. Ha G fa, akkor fatámasznak hívjuk, és ez egy minimális fatámasz, ha élének súlya egy adott élsúly-függvény. A hipergráfok fa támogatásának számos alkalmazása van, a szociális háló elemzésétől és a hálózat tervezési problémáitól kezdve a hipergráfok és Euler diagramok megjelenítéséig. Különösen megmutatjuk, hogyan lehet egy minimális súlyú fa tartással létrehozni egy olyan területarányos Euler-diagramot, amely kielégíti a tipikus jól formázási feltételeket, és emellett minimalizálja az Euler-diagramban a beállított határok egyidejű görbéinek számát.

minimális

Kulcsszavak

Előnézet

Nem lehet megjeleníteni az előnézetet. Előnézet PDF letöltése.