MPI-INF D1 Publications: Journal Article: Connecting face hitting sets in planar graphs

Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

Options:

Library locked

Goto entry point

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

Edit History (please click the blue arrow to see the details)

	Editor(s) [Library]	Created 02/11/2011 01:34:03
Revision 1. 0.	Editor Anja Becker Pascal Schweitzer	Edit Date 15.02.2011 13:05:48 02/11/2011 01:34:03 AM

Attachment Section