Computing role assignments of proper interval graphs in polynomial time

DOI10.1016/J.JDA.2011.12.004MaRDI QIDQ450561zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

proper interval graphlocally surjective homomorphismRole Assignment

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(14)

• Complexity of the game domination problem
• Parameterizing role coloring on forests
• Computing role assignments of proper interval graphs in polynomial time
• An algorithmic framework for locally constrained homomorphisms
• Computing role assignments of split graphs
• scientific article; zbMATH DE number 2038757 (Why is no real title available?)
• Role coloring bipartite graphs
• scientific article; zbMATH DE number 1302393 (Why is no real title available?)
• Making Role Assignment Feasible: A Polynomial-Time Algorithm for Computing Ecological Colorings
• 2-role assignments on triangulated graphs.
• Intersection graphs of non-crossing paths
• 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)