de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Enumerating Spanning and Connected Subsets in Graphs and Matroids

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44374

Elbassioni,  Khaled
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Khachiyan, L., Boros, E., Borys, K., Elbassioni, K., Gurvich, V., & Makino, K. (2006). Enumerating Spanning and Connected Subsets in Graphs and Matroids. In Algorithms - ESA 2006, 14th Annual European Symposium (pp. 444-455). Berlin, Germany: Springer.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-22B3-A
Zusammenfassung
We show that enumerating all minimal spanning and connected subsets of a given matroid can be solved in incremental quasi-polynomial time. In the special case of graphical matroids, we improve this complexity bound by showing that all minimal $2$-vertex connected subgraphs of a given graph can be generated in incremental polynomial time.