Computing Role Assignments of Proper Interval Graphs in Polynomial Time

DOI10.1007/978-3-642-19222-7_18zbMath1326.68159OpenAlexW2178299939MaRDI QIDQ3000505

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

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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A complete complexity classification of the role assignment problem
• 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
• 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
• 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