Vi anser att problemen med att hitta optimala identifieringskoder, (öppna) lokalisera-dominerande uppsättningar och lösa uppsättningar (betecknade identifiera kod, (öppna) lokalisera-Dominering Set och Metrisk dimension) av ett intervall eller en permutation diagram. I dessa problem, ber man att skilja alla hörn av en graf med en delmängd av hörnen, med antingen grannskapet inom den lösning som eller avstånden till lösningen hörn. Med hjälp av en generell minskning för denna klass av problem, visar vi att de beslutsproblem som är förknippade med dessa fyra begrepp är NP-komplett, även för intervallgrafer av diameter 2 och permutationsgrafer av diameter 2. Samtidigt som identifieringskoden och (Open) lokalisering-Doming Set är trivialt fast-parameter-dragbar när parameteriserad av lösningsstorlek, är det känt att i samma inställning Metrisk Dimension är W [2]-hård. Vi visar att för intervallgrafer, denna parameterisering av Metrisk Dimension är fast-parameter-dragbar.
Komplexiteten i att identifiera koder i enhetsintervalldiagram är förvånansvärt fortfarande öppen REF (men har visat sig vara NP-komplett för intervalldiagram).
Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity
{'venue': 'Algorithmica 78(3):914-944 (2017)', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}