15 citations · 57 across the 24 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2019★ 3 cited
Average-case complexity of a branch-and-bound algorithm for min dominating set
Tom Denat, Ararat Harutyunyan, Vangelis Th. Paschos
The average-case complexity of a branch-and-bound algorithms for Minimum Dominating Set problem in random graphs in the G(n,p) model is studied. We identify phase transitions betwe…
cs.DS2018
Maximum Independent Sets in Subcubic Graphs: New Results
Ararat Harutyunyan, Michael Lampis, Vadim Lozin +1
The maximum independent set problem is known to be NP-hard in the class of subcubic graphs, i.e. graphs of vertex degree at most 3. We present a polynomial-time solution in a subcl…
cs.DS2016★ 11 cited
The complexity of tropical graph homomorphisms
Florent Foucaud, Ararat Harutyunyan, Pavol Hell +3
A tropical graph consists of a graph and a (not necessarily proper) vertex-colouring of . Given two tropical graphs and , a homomorphism of $(G,…