

























The Sitting Closer to Friends than Enemies (SCFE) problem is to find an embedding in a metric space for the vertices of a given signed graph so that, for every pair of incident edges with different sign, the positive edge is shorter (in the metric of the space) than the negative edge. In this document, we present new results regarding the SCFE problem when the metric space in consideration is the circumference. Our main results say that, given a signed graph, it is NP-complete to decide whether such an embedding exists in the circumference or not. Nevertheless, if the given signed graph is complete, then such decision can be made in polynomial time. In particular, we prove that, given a complete signed graph, it has such an embedding if and only if its positive part is a proper circular arc graph.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。