Noncrossing k-factors in geometric graphs. I

Noncrossing k-factors in geometric graphs. I

0.00 Avg rating—0 Votes
Article ID: iaor20051509
Country: Belarus
Volume: 3
Start Page Number: 94
End Page Number: 99
Publication Date: Sep 2004
Journal: Proceedings of the National Academy of Sciences of Belarus, Series of Physical-Mathematical Sciences
Authors:
Abstract:

It is proved that deciding the existence of a noncrossing 1-factor in orthogonal geometric graph G with r(G)≥1, the existence of a noncrossing 3-factor in 4-regular geometric graph G with r(G)≥1 and the existence of a noncrossing 2-factor in geometric graph G with r(G)≥1, where r(G) is the index of intersection of geometric graph G, are NP-complete.

Reviews

Required fields are marked *. Your email address will not be published.