Computing role assignments of chordal graphs

Pim van 't Hof; Daniël Paulusma; Johan M.M. van Rooij

doi:10.1016/j.tcs.2010.05.041

Computing role assignments of chordal graphs

Pim van 't Hof
, Daniël Paulusma^*
, Johan M.M. van Rooij

^*Corresponding author for this work

Research output: Contribution to journal › Article › Academic › peer-review

15 Citations (Scopus)

10 Downloads (Pure)

Abstract

In social network theory, a simple graph G is called k-role assignable if there is a surjective mapping that assigns a number from {1,...,k} , called a role, to each vertex of G such that any two vertices with the same role have the same sets of roles assigned to their neighbors. The decision problem whether such a mapping exists is called the
k-Role Assignment problem. This problem is known to be NP-complete for any fixed k≥2. In this paper, we classify the computational complexity of the k-Role Assignment problem for the class of chordal graphs. We show that for this class the problem can be solved in linear time for k = 2, , but remains NP-complete for any k≥3. This generalizes earlier results by Sheng and answers her open problem.

Original language	English
Pages (from-to)	3601-3613
Number of pages	13
Journal	Theoretical computer science
Volume	411
Issue number	40-42
Early online date	8 Jun 2010
DOIs	https://doi.org/10.1016/j.tcs.2010.05.041
Publication status	Published - 6 Sept 2010
Externally published	Yes

Access to Document

10.1016/j.tcs.2010.05.041Licence: Elsevier licence

Computing role assignments of chordal graphs
van 't Hof, P., Paulusma, D. & Rooij, J. M. M. V., 2009, Fundamentals of Computation Theory, 17th International Symposium, FCT 2009, Wroclaw, Poland, September 2-4, 2009. Proceedings. Kutylowski, M., Charatonik, W. & Gebala, M. (eds.). Springer, p. 193-204 12 p. (Lecture Notes in Computer Science; vol. 5699).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Cite this

@article{cb6774d3604d44778044a70726959fa9,

title = "Computing role assignments of chordal graphs",

abstract = "In social network theory, a simple graph G is called k-role assignable if there is a surjective mapping that assigns a number from \{1,...,k\} , called a role, to each vertex of G such that any two vertices with the same role have the same sets of roles assigned to their neighbors. The decision problem whether such a mapping exists is called the k-Role Assignment problem. This problem is known to be NP-complete for any fixed k≥2. In this paper, we classify the computational complexity of the k-Role Assignment problem for the class of chordal graphs. We show that for this class the problem can be solved in linear time for k = 2, , but remains NP-complete for any k≥3. This generalizes earlier results by Sheng and answers her open problem.",

author = "\{van 't Hof\}, Pim and Dani{\"e}l Paulusma and Rooij, \{Johan M.M. van\}",

year = "2010",

month = sep,

day = "6",

doi = "10.1016/j.tcs.2010.05.041",

language = "English",

volume = "411",

pages = "3601--3613",

journal = "Theoretical computer science",

issn = "0304-3975",

publisher = "Elsevier",

number = "40-42",

}

TY - JOUR

T1 - Computing role assignments of chordal graphs

AU - van 't Hof, Pim

AU - Paulusma, Daniël

AU - Rooij, Johan M.M. van

PY - 2010/9/6

Y1 - 2010/9/6

N2 - In social network theory, a simple graph G is called k-role assignable if there is a surjective mapping that assigns a number from {1,...,k} , called a role, to each vertex of G such that any two vertices with the same role have the same sets of roles assigned to their neighbors. The decision problem whether such a mapping exists is called the k-Role Assignment problem. This problem is known to be NP-complete for any fixed k≥2. In this paper, we classify the computational complexity of the k-Role Assignment problem for the class of chordal graphs. We show that for this class the problem can be solved in linear time for k = 2, , but remains NP-complete for any k≥3. This generalizes earlier results by Sheng and answers her open problem.

AB - In social network theory, a simple graph G is called k-role assignable if there is a surjective mapping that assigns a number from {1,...,k} , called a role, to each vertex of G such that any two vertices with the same role have the same sets of roles assigned to their neighbors. The decision problem whether such a mapping exists is called the k-Role Assignment problem. This problem is known to be NP-complete for any fixed k≥2. In this paper, we classify the computational complexity of the k-Role Assignment problem for the class of chordal graphs. We show that for this class the problem can be solved in linear time for k = 2, , but remains NP-complete for any k≥3. This generalizes earlier results by Sheng and answers her open problem.

U2 - 10.1016/j.tcs.2010.05.041

DO - 10.1016/j.tcs.2010.05.041

M3 - Article

SN - 0304-3975

VL - 411

SP - 3601

EP - 3613

JO - Theoretical computer science

JF - Theoretical computer science

IS - 40-42

ER -

Computing role assignments of chordal graphs

Abstract

Access to Document

Fingerprint

Research output

Computing role assignments of chordal graphs

Cite this