Computing role assignments of proper interval graphs in polynomial time

DOI10.1016/j.jda.2011.12.004zbMath1247.05240OpenAlexW2021148840MaRDI QIDQ450561

Daniël Paulusma, Pinar Heggernes, Pim van 't Hof

Publication date: 13 September 2012

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2011.12.004

zbMATH Keywords

proper interval graphlocally surjective homomorphismRole Assignment

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

Computing role assignments of split graphs ⋮ Parameterizing role coloring on forests ⋮ Complexity of the game domination problem ⋮ An algorithmic framework for locally constrained homomorphisms ⋮ Intersection graphs of non-crossing paths ⋮ Role coloring bipartite graphs ⋮ Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simple linear time recognition of unit interval graphs
• A complete complexity classification of the role assignment problem
• Counting the number of independent sets in chordal graphs
• Finite planar emulators for \(K_{4,5} - 4K_{2}\) and \(K_{1,2,2,2}\) and Fellows' conjecture
• Comparing universal covers in polynomial time
• The clique-separator graph for chordal graphs
• Role colouring a graph
• Covering regular graphs
• 2-role assignments on triangulated graphs.
• Algorithmic graph theory and perfect graphs
• Optimal greedy algorithms for indifference graphs
• Incidence matrices and interval graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Representation of a finite graph by a set of intervals on the real line
• Graph Labelings Derived from Models in Distributed Computing
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Graph Classes: A Survey
• Partial covers of graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• The role assignment model nearly fits most social networks
• Fixed-parameter complexity of \(\lambda\)-labelings

This page was built for publication: Computing role assignments of proper interval graphs in polynomial time