Computer Science – Discrete Mathematics
Scientific paper
2011-04-19
Computer Science
Discrete Mathematics
Scientific paper
We introduce the concept of shallow directed minors and based on this a new classification of classes of directed graphs which is diametric to existing directed graph decompositions and width measures proposed in the literature. We then study in depth one type of classes of directed graphs which we call nowhere crownful. The classes are very general as they include, on one hand, all classes of directed graphs whose underlying undirected class is nowhere dense, such as planar, bounded-genus, and $H$-minor-free graphs; and on the other hand, also contain classes of high edge density whose underlying class is not nowhere dense. Yet we are able to show that problems such as directed dominating set and many others become fixed-parameter tractable on nowhere crownful classes of directed graphs. This is of particular interest as these problems are not tractable on any existing digraph measure for sparse classes. The algorithmic results are established via proving a structural equivalence of nowhere crownful classes and classes of graphs which are directed uniformly quasi-wide. This rather surprising result is inspired by Nesetril and Ossana de Mendez (2008) and yet a different and more delicate proof is needed, which is a significant part of our contribution.
Kreutzer Stephan
Tazari Siamak
No associations
LandOfFree
Directed Nowhere Dense Classes of Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Directed Nowhere Dense Classes of Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Directed Nowhere Dense Classes of Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-183705