English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Tolerance graphs model interval relations in such a way that intervals cantolerate a certain amount of overlap without being in conflict. In one of themost natural generalizations of tolerance graphs with direct applications inthe comparison of DNA sequences from different organisms, namely multitolerancegraphs, two tolerances are allowed for each interval - one from the left andone from the right side. Several efficient algorithms for optimization problemsthat are NP-hard in general graphs have been designed for tolerance andmultitolerance graphs. In spite of this progress, the complexity status of somefundamental algorithmic problems on tolerance and multitolerance graphs, suchas the dominating set problem, remained unresolved until now, three decadesafter the introduction of tolerance graphs. In this article we introduce twonew geometric representations for tolerance and multitolerance graphs, given bypoints and line segments in the plane. Apart from being important on their own,these new representations prove to be a powerful tool for deriving bothhardness results and polynomial time algorithms. Using them, we surprisinglyprove that the dominating set problem can be solved in polynomial time ontolerance graphs and that it is APX-hard on multitolerance graphs, solving thusa longstanding open problem. This problem is the first one that has beendiscovered with a different complexity status in these two graph classes.

New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs