Computing role assignments of split graphs

DOI10.1016/J.TCS.2016.05.011MaRDI QIDQ287443zbMATH OpenOpenAlexFDO

Authors Mitre C. Dourado

Publication date 26 May 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2016.05.011

zbMATH Keywords

social networksgraph algorithmsNP-complete problemsrole assignmentssplit graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Computing role assignments of chordal graphs
• Computing Role Assignments of Chordal Graphs
• How hard is it to determine if a graph has a 2-role assignment?
• The role assignment model nearly fits most social networks
• Computing some role assignments of Cartesian product of graphs

Cites work

• scientific article; zbMATH DE number 1003286 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 2080268 (Why is no real title available?)
• scientific article; zbMATH DE number 1496855 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 1456953 (Why is no real title available?)
• 2-role assignments on triangulated graphs.
• A complete complexity classification of the role assignment problem
• Algorithmic graph theory and perfect graphs
• Clustering and domination in perfect graphs
• Comparing universal covers in polynomial time
• Computing role assignments of chordal graphs
• Computing role assignments of proper interval graphs in polynomial time
• Dominating sets for split and bipartite graphs
• Graph Transformations
• Graph theory
• HAMILTONian circuits in chordal bipartite graphs
• How hard is it to determine if a graph has a 2-role assignment?
• Introduction to algorithms.
• Local computations in graphs: the case of cellular edge local computations
• Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
• Role colouring a graph
• Some simplified NP-complete graph problems
• The role assignment model nearly fits most social networks
• The splittance of a graph

Cited in

(14)

• 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 proper interval graphs in polynomial time
• Role coloring bipartite graphs
• Computing role assignments of chordal graphs
• scientific article; zbMATH DE number 1302393 (Why is no real title available?)
• The role assignment model nearly fits most social networks
• Computing a 3-role assignment is polynomial-time solvable on complementary prisms
• Role colouring graphs in hereditary classes
• On the number of maximal independent sets in minimum colorings of split graphs
• An algorithmic framework for locally constrained homomorphisms
• Computing Role Assignments of Chordal Graphs
• How hard is it to determine if a graph has a 2-role assignment?

This page was built for publication: Computing role assignments of split graphs

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