Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor(s)

Author(s):

Schweitzer, Pascal
Schweitzer, Patrick

dblp
dblp

Not MPG Author(s):

Schweitzer, Patrick

BibTeX cite key*:

SchweitzerSchweitzer2010

Title

Title*:

Connecting face hitting sets in planar graphs

Journal

Journal Title*:

Information Processing Letters

Journal's URL:

www.elsevier.com/locate/ipl

Download URL
for the article:

http://dx.doi.org/10.1016/j.ipl.2010.10.008

Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:

www.elsevier.com

Publisher's
Address:

Amsterdam

ISSN:

0020-0190

Vol, No, pp, Date

Volume*:

111

Number:

1

Publishing Date:

December 2010

Pages*:

11-15

Number of
VG Pages:

5

Page Start:

11

Page End:

15

Sequence Number:


DOI:

10.1016/j.ipl.2010.10.008

Note, Abstract, ©

Note:


(LaTeX) Abstract:

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.

URL for the Abstract:


Categories,
Keywords:

Combinatorial problems, Planar graph, Face hitting set

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{SchweitzerSchweitzer2010,
AUTHOR = {Schweitzer, Pascal and Schweitzer, Patrick},
TITLE = {Connecting face hitting sets in planar graphs},
JOURNAL = {Information Processing Letters},
PUBLISHER = {Elsevier},
YEAR = {2010},
NUMBER = {1},
VOLUME = {111},
PAGES = {11--15},
ADDRESS = {Amsterdam},
MONTH = {December},
ISBN = {0020-0190},
DOI = {10.1016/j.ipl.2010.10.008},
}


Entry last modified by Anja Becker, 02/15/2011
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
02/11/2011 01:34:03 AM
Revision
1.
0.


Editor
Anja Becker
Pascal Schweitzer


Edit Date
15.02.2011 13:05:48
02/11/2011 01:34:03 AM


Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section