11 citations · 11 across the 2 of their papers we have counts for
4 papers
What Makes the Recognition Problem Hard for Classes Related to Segment and String graphs?
Irina Mustata, Martin Pergel
We explore what could make recognition of particular intersection-defined classes hard. We focus mainly on unit grid intersection graphs (UGIGs), i.e., intersection graphs of unit-…
The Complexity of the Partial Order Dimension Problem - Closing the Gap
Stefan Felsner, Irina Mustata, Martin Pergel
The dimension of a partial order is the minimum number of linear orders whose intersection is . There are efficient algorithms to test if a partial order has dimension at mo…
Unit Grid Intersection Graphs: Recognition and Properties
Irina Mustaţă, Martin Pergel
It has been known since 1991 that the problem of recognizing grid intersection graphs is NP-complete. Here we use a modified argument of the above result to show that even if we re…
On a game on graphs
Felix Günther, Irina Mustata
We start with the well-known game below: Two players hold a sheet of paper to their forehead on which a positive integer is written. The numbers are consecutive and each player can…