Computing role assignments of proper interval graphs in polynomial time

DOI10.1016/J.JDA.2011.12.004zbMATH Open1247.05240OpenAlexW2021148840MaRDI QIDQ450561FDOQ450561

Authors: Pinar Heggernes, Daniël Paulusma, 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

Recommendations

• Computing role assignments of proper interval graphs in polynomial time
• Computing Role Assignments of Chordal Graphs
• Computing role assignments of chordal graphs
• scientific article; zbMATH DE number 2038757
• Computing role assignments of split graphs

zbMATH Keywords

proper interval graphlocally surjective homomorphismRole Assignment

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Graph Classes: A Survey
• 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
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Title not available (Why is that?)
• Simple linear time recognition of unit interval graphs
• Representation of a finite graph by a set of intervals on the real line
• Role colouring a graph
• 2-role assignments on triangulated graphs.
• Local computations in graphs: the case of cellular edge local computations
• The role assignment model nearly fits most social networks
• A complete complexity classification of the role assignment problem
• Comparing universal covers in polynomial time
• The clique-separator graph for chordal graphs
• Fixed-parameter complexity of \(\lambda\)-labelings
• Covering regular graphs
• Partial covers of graphs
• Graph Labelings Derived from Models in Distributed Computing
• 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

Cited In (14)

• Parameterizing role coloring on forests
• Complexity of the game domination problem
• Computing role assignments of proper interval graphs in polynomial time
• An algorithmic framework for locally constrained homomorphisms
• Title not available (Why is that?)
• Computing role assignments of split graphs
• Role coloring bipartite graphs
• Title not available (Why is that?)
• Making Role Assignment Feasible: A Polynomial-Time Algorithm for Computing Ecological Colorings
• Intersection graphs of non-crossing paths
• 2-role assignments on triangulated graphs.
• An algorithmic framework for locally constrained homomorphisms
• Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
• Computing Role Assignments of Chordal Graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q450561)