EUVIMEDEUVIMED entdecken
Crossref

Some NP-complete Edge Packing and Partitioning Problems in Planar Graphs

Jed Yang

Communications on Number Theory and Combinatorial Theory · 2022

DOI: 10.70013/m9rx1zq8 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Communications on Number Theory and Combinatorial Theory, 2022. Verfasst von Jed Yang.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Graph packing and partitioning problems have been studied in many contexts, including from the algorithmic complexity perspective. Consider the packing problem of determining whether a graph contains a spanning tree and a cycle that do not share edges. Bernáth and Király proved that this decision problem is NP-complete and asked if the same result holds when restricting to planar graphs. Similarly, they showed that the packing problem with a spanning tree and a path between two distinguished vertices is NP-complete. They also established the NP-completeness of the partitioning problem of determining whether the edge set of a graph can be partitioned into a spanning tree and a (not-necessarily spanning) tree. We prove that all three problems remain NP-complete even when restricted to planar graphs.

Zitieren

APA

Yang, J. (2022). Some NP-complete Edge Packing and Partitioning Problems in Planar Graphs. Communications on Number Theory and Combinatorial Theory. https://doi.org/10.70013/m9rx1zq8

Vancouver

Yang J. Some NP-complete Edge Packing and Partitioning Problems in Planar Graphs. Communications on Number Theory and Combinatorial Theory. 2022. doi:10.70013/m9rx1zq8

BibTeX
@article{Yang2022,
  author = {Yang, Jed},
  title = {Some NP-complete Edge Packing and Partitioning Problems in Planar Graphs},
  journal = {Communications on Number Theory and Combinatorial Theory},
  year = {2022},
  doi = {10.70013/m9rx1zq8}
}
Kostenlos starten →