Workshop on Graph Modification
algorithms, experiments and new problems

23rd - 24th January 2020, Bergen, Norway

• Home
• Call for presentations
• Comittees
  
• Important dates
• Pratical information
• Registration
• Participants
  
• Program
  
• Contacts

Program

Talks will start on Thursday 23rd at 9.00 and will end on Friday 24th at 18.20.

Keynotes

---

Ulrik Brandes

ETH Zurich

Social Networks, First Principles, and Graph Modification

Social network analysis is an applied network science, so that graphs take center stage as a data representation. After a brief introduction to the field, I will develop some of the more common forms of analysis such as centrality, roles, and clustering from first principles, and highlight graph modification problems along the way.

Biography

Ulrik Brandes is Professor for Social Networks in the Department of Humanities, Social and Political Sciences at ETH Zurich. His background is in algorithmics, with special interests in graph algorithms and network visualization. After 15 years as a professor in computer science, also teaching courses such Theory of Computing and Algorithms and Data Structures, he finally gave himself up entirely to his passion for social network science. Methodology and method development in this area are complemented by a growing interest in societal challenges arising from the Digital Transformation.

Martin Milanič

University of Primorska

Edge elimination schemes of weighted graph classes

In 2017, Laurent and Tanigawa extended to weighted graphs the classical notion of perfect elimination ordering for graphs, giving a framework capturing common vertex elimination orderings of families of chordal graphs, Robinsonian matrices, and ultrametrics. They show that an edge-weighted graph G has a perfect elimination ordering if and only if it has a vertex ordering that is a simultaneous perfect elimination ordering of all its level graphs, where the level graph of G is any graph obtained from G by removing all sufficiently light edges. In particular, this latter condition implies that all the level graphs must be chordal. We generalize this definition as follows. Given a graph class C, we say that an edge-weighted graph is level-C if all its level graphs are in C. A particularly nice situation occurs when all the edges of an edge-weighted level-C graph can be eliminated one at a time, from lightest to heaviest, so that all the intermediate graphs are in C. Such an edge elimination ordering is called a sorted perfect edge elimination ordering. We show that if C is the class of threshold graphs, split graphs, chordal graphs, or their complements, then every level-C edge-weighted graph has a sorted perfect edge elimination ordering. Our constructive proofs are based on a generalization of the concept of monotone graph classes. We say that a graph class C is gap monotone if for every two graphs G and G' in C such that G is a spanning subgraph of G', graph G can be obtained from G' by a sequence of edge deletions such that all intermediate graphs are in C. We show that, in contrast with many other well known classes of perfect graphs, the classes of threshold graphs, split graphs, and chordal graphs are gap monotone.  This is a joint work with J. Beisegel, N. Chiarelli, E. Köhler, M. Krnc, N. Pivač, R. Scheffler, and M. Strehler.

Biography

Martin Milanič is a Full Professor at the University of Primorska in Koper, Slovenia. After getting his diploma at the University of Ljubljana in 2003, he went to Rutgers University in New Jersey, where he earned his PhD in 2007 with his thesis "Algorithmic Developments and Complexity Results for Finding Maximum and Exact Independent Sets in Graphs". Between 2007 and 2009, he was a postdoc researcher in Germany at Bielefeld University. In 2009, he became Assistant Professor and Research Fellow at the University of Primorska. Between 2013 and 2014, he was also a Research Fellow at the Institute of Mathematics, Physics and Mechanics (IMFM) in Ljubljana. Since 2019, he is a Full Professor at the Faculty of Mathematics, Natural Sciences and Information Technologies and a Research Counsellor at the Andrej Marušič Institute of the University of Primorska. His research interests lie in algorithmic graph theory, the study of independence and domination graph invariants, the structure and characterization of graphs in hereditary classes, and applications of combinatorial optimization and graph theory to computational biology. In 2017 he was awarded a Zois Certificate of Recognition for important achievements in scientific research work in the field of discrete mathematics. He is editorial board member of Discrete Applied Mathematics, Ars Mathematica Contemporanea, and The Art of Discrete and Applied Mathematics.

Program of the workshop

---

---