The exponential time complexity of computing the probability that a graph is connected

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

Abstract

We show that computation of all-terminal graph reliability requires time exponential in Ω(m/ log2 m) for simple graphs of m edges under the Exponential Time Hypothesis.

Detaljer

Författare
Enheter & grupper
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)
Originalspråkengelska
Titel på värdpublikationLecture Notes in Computer Science
FörlagSpringer
Sidor192-203
Antal sidor11
Volym6198
StatusPublished - 2010
PublikationskategoriForskning
Peer review utfördJa
Evenemang5th International Symposium on Parameterized and Exact Computation (IPEC 2010) - Chennai, Indien
Varaktighet: 2010 dec 132010 dec 15

Publikationsserier

Namn
Volym6198

Konferens

Konferens5th International Symposium on Parameterized and Exact Computation (IPEC 2010)
LandIndien
OrtChennai
Period2010/12/132010/12/15