Selected Publications

2014

  • P. Hell. Graph Partitions with Prescribed Patterns. Eur. J. Comb., 35: 335-353 (2014).

2013

  • S. Das, M. C. Francis, P. Hell, Jing Huang. Recognition and Characterization of Chronological Interval Digraphs. Electr. J. Comb., 20(3): P5 (2013).
  • T. Feder, P. Hell, S. N. Rizi. Obstructions to Partitions of Chordal Graphs. Discrete Mathematics, 313(19): 1861-1871 (2013).
  • H. Akbari, P. Berenbrink. Parallel Rotor Walks on Finite Graphs and Applications in Discrete Load Balancing. SPAA, 186-195 (2013).
  • P. A. Golovach, P. Heggernes, D. Kratsch, A. Rafiey. Cliques and Clubs. CIAC, 276-287 (2013).

2012

  • P. Hell, A. Rafiey. Monotone Proper Interval Digraphs and Min-Max Orderings. SIAM J.Discrete Math 26(4) 1576-1596 (2012).
  • P. Hell, A. Rafiey. The Dichotomy of Minimum Cost Homomorphism Problems for Digraphs. SIAM J.Discrete Math., 26(4) 1597-1608 (2012).
  • T. Feder, P.Hell, J. Huang, A. Rafiey. Interval Graphs, Adjusted Interval Digraphs, and Reflexive List Homomorphisms. Discrete Applied Mathematics, 160(6): 697-707 (2012),
  • P. Hell, M. Mastrolilli, M. M. Nevisi, A. Rafiey. Approximation of minimum cost homomorphisms. ESA, (2012).
  • P. Hell, M. Hermann, M. M. Nevisi. Counting Partitions of Graphs. ISAAC, 227-236 (2102).
  • Petra Berenbrink, Colin Cooper, Tom Friedetzky: Random Walks which Prefer Unvisited Edges: Exploring High Girth Even Degree Expanders in Linear Time. PODC, 29-36 (2012).

2011

  • H. A. Harutyunyan, P.Hell, A. L. Liestman. Messy Broadcasting - Decentralized Broadcast Schemes with Limited Knowledge. Discrete Applied Mathematics, 159(5): 322-327 (2011).
  • P. Hell, A. Rafiey. The Dichotomy of List Homomorphisms for Digraphs. SODA, 1703-1713 (2011).
  • M. Groshaus, P. Hell, S. Klein, L. T. Nogueira, F. Protti. Cycle Transversals in Bounded Degree Graphs. Discrete Mathematics & Theoretical Computer Science, 13(1): 45-66 (2011).

2010

  • T. Feder, P. Hell, P. Jonsson, A. A. Krokhin, G. Nordh. Retractions to Pseudoforests. SIAM J. Discrete Math., 24(1): 101-112 (2010).
  • M. D. Coury, P. Hell, J. Kratochvíl, T. Vyskocil. Faithful Representations of Graphs by Islands in the Extended Grid. LATIN, 131-142 (2010).
  • P. Berenbrink, C. Cooper, R. Elsässer, T. Radzik, T. Sauerwald. Speeding Up Random Walks with Neighborhood Exploration. SODA, 1422-1435 (2010).

2009

  • P. Hell, D. G. Kirkpatrick. Linear-time Certifying Algorithms for Near-graphical Sequences. Discrete Mathematics, 309(18): 5703-5713 (2009).
  • P. Hell, Z. Pan, T. Wong, X. Zhu. Adaptable Chromatic Number of Graph Products. Discrete Mathematics, 309(21): 6153-6159 (2009).
2008

  • G. Gutin, P. Hell, A. Rafiey, A. Yeo. A Dichotomy for Minimum Cost Graph Homomorphisms. Eur. J. Comb., 29(4): 900-911 (2008).
  • R. C. Brewster, T. Feder, P. Hell, J. Huang, G. MacGillivray. Near-Unanimity Functions and Varieties of Reflexive Graphs. SIAM J. Discrete Math., 22(3): 938-960 (2008).
  • A. Gupta, P. Hell, M. Karimi, A. Rafiey. Minimum Cost Homomorphisms to Reflexive Digraphs. LATIN, 182-193 (2008).
  • F. Ergün, H. Jowhari. On Distance to Monotonicity and Longest Increasing Subsequence of a Data Stream. SODA, 730-736 (2008).