Computing role assignments of proper interval graphs in polynomial time

DOI10.1007/978-3-642-19222-7_18MaRDI QIDQ3000505zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, Pim Van 't Hof, Daniël Paulusma

Publication date 19 May 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://dro.dur.ac.uk/18308/1/18308.pdf

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

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

Cites work

• 2-role assignments on triangulated graphs.
• A complete complexity classification of the role assignment problem
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Algorithmic graph theory and perfect graphs
• Comparing universal covers in polynomial time
• 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
• scientific article; zbMATH DE number 3005477 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• Incidence matrices and interval graphs
• Local computations in graphs: the case of cellular edge local computations
• Partial covers of graphs
• Representation of a finite graph by a set of intervals on the real line
• Role colouring a graph
• 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

(5)

• Computing Role Assignments of Chordal Graphs
• scientific article; zbMATH DE number 1302393 (Why is no real title available?)
• scientific article; zbMATH DE number 2038757 (Why is no real title available?)
• Computing role assignments of proper interval graphs in polynomial time
• Making Role Assignment Feasible: A Polynomial-Time Algorithm for Computing Ecological Colorings

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 Q3000505)