Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Connecting Face Hitting Sets in Planar Graphs

Schweitzer, P., & Schweitzer, P. (2010). Connecting Face Hitting Sets in Planar Graphs. Information Processing Letters, 111(1), 11-15. doi:10.1016/j.ipl.2010.10.008.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-162F-4 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-2648-2
Genre: Zeitschriftenartikel

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Schweitzer, Pascal1, Autor           
Schweitzer, Patrick2, Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: We show that any face hitting set of size n of a connected planar graph with a minimum degree of at least 3 is contained in a connected subgraph of size 5n−6. Furthermore we show that this bound is tight by providing a lower bound in the form of a family of graphs. This improves the previously known upper and lower bound of 11n−18 and 3n respectively by Grigoriev and Sitters. Our proof is valid for simple graphs with loops and generalizes to graphs embedded in surfaces of arbitrary genus.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 20102010
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 536820
DOI: 10.1016/j.ipl.2010.10.008
URI: http://dx.doi.org/10.1016/j.ipl.2010.10.008
Anderer: Local-ID: C1256428004B93B8-BA81420A8DFBE16DC125783400031E2C-SchweitzerSchweitzer2010
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Information Processing Letters
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: Amsterdam : Elsevier
Seiten: - Band / Heft: 111 (1) Artikelnummer: - Start- / Endseite: 11 - 15 Identifikator: ISSN: 0020-0190