BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260911T220541Z
UID:Seminar-dept-307@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20130110T160000
DTEND:20130110T170000
SUMMARY:School Seminar Series
DESCRIPTION:Dr. Christopher Thraves Caro: Signed graph embedding, when everybody can sit closer to friends than enemies\n\nSigned graphs are graphs with signed edges. They are commonly used to\n\nrepresent positive and negative relationships in social networks. While\n\nbalance theory and clusterizable graphs deal with signed graphs, recent\n\nempirical studies have proved that they fail to reflect some current\n\npractices in real social networks. In this presentation we address the\n\nissue of drawing signed graphs and capturing such social interactions. We\n\nrelax the previous assumptions to define an embedding as a model in which\n\nevery vertex has to be placed closer to its neighbors connected via a\n\npositive edge than its neighbors connected via a negative edge in the\n\nresulting space. Based on this definition, we address the problem of\n\ndeciding whether a given signed graph has a drawing in the 1-dimensional\n\nEuclidean space. We provide a polynomial time algorithm that decides if a\n\ngiven complete signed graph has a drawing, and provides it when\n\napplicable. When the input signed graph is not complete the\n\nrecognition problem has\n\nbeen proved to be NP-complete. We provide a greedy heuristic that shows\n\ninteresting recognition capabilities when the input is not complete.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=307
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR