On the Power of Isolation in Planar Graphs
ACM Transactions on Computation Theory · 2011
DOI: 10.1145/2003685.2003687 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Computation Theory, 2011. Verfasst von Raghav Kulkarni. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 18 Literaturangaben.
Abstract (Originalsprache)
We study (deterministic) isolation for certain structures in directed and undirected planar graphs. The motivation for undertaking such a study comes from recent positive results on this topic. For example: Bourke et al. [2009] isolate a directed path in planar graphs and subsequently Datta et al. [2010b] isolate a perfect matching in bipartite planar graphs. Our first observation is that sufficiently strong (and plausible) isolations for certain structures in planar graphs would have strong consequences such as: NL ⊆ ⊕ L , Bipartite-Matching ∈ NC , and NP ⊆ ⊕ P . Our second observation is that although we do not yet have such strong isolations for arbitrary planar graphs, we do have them for bipartite planar graphs, that is, non-bipartiteness is the main bottleneck.
Zitieren
APA
Kulkarni, R. (2011). On the Power of Isolation in Planar Graphs. ACM Transactions on Computation Theory. https://doi.org/10.1145/2003685.2003687
Vancouver
Kulkarni R. On the Power of Isolation in Planar Graphs. ACM Transactions on Computation Theory. 2011. doi:10.1145/2003685.2003687
BibTeX
@article{Kulkarni2011,
author = {Kulkarni, Raghav},
title = {On the Power of Isolation in Planar Graphs},
journal = {ACM Transactions on Computation Theory},
year = {2011},
doi = {10.1145/2003685.2003687}
}
EUVIMED