EUVIMEDEUVIMED entdecken
Crossref

On the Power of Isolation in Planar Graphs

Raghav Kulkarni

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →