Loading Events

« All Events

  • This event has passed.
:

O-joung Kwon (권오정), Classes of intersection digraphs with good algorithmic properties

June 8 Tuesday @ 3:00 PM - 4:00 PM KST

Zoom ID: 875 9395 3555 (relay)

Speaker

O-joung Kwon (권오정)
Incheon National University & IBS Discrete Mathematics Group
http://ojkwon.com

An intersection digraph is a digraph where every vertex $v$ is represented by an ordered pair $(S_v, T_v)$ of sets such that there is an edge from $v$ to $w$ if and only if $S_v$ and $T_w$ intersect. An intersection digraph is reflexive if $S_v\cap T_v\neq \emptyset$ for every vertex $v$. Compared to well-known undirected intersection graphs like interval graphs and permutation graphs, not many algorithmic applications on intersection digraphs have been developed.

Motivated by the successful story on algorithmic applications of intersection graphs using a graph width parameter called mim-width, we introduce its directed analogue called `bi-mim-width’ and prove that various classes of reflexive intersection digraphs have bounded bi-mim-width. In particular, we show that as a natural extension of $H$-graphs, reflexive $H$-digraphs have linear bi-mim-width at most $12|E(H)|$, which extends a bound on the linear mim-width of $H$-graphs [On the Tractability of Optimization Problems on $H$-Graphs. Algorithmica 2020]

For applications, we introduce a novel framework of directed versions of locally checkable problems, that streamlines the definitions and the study of many problems in the literature and facilitates their common algorithmic treatment. We obtain unified polynomial-time algorithms for these problems on digraphs of bounded bi-mim-width, when a branch decomposition is given. Locally checkable problems include Kernel, Dominating Set, and Directed $H$-Homomorphism.

This seminar is a part of the
Round the World Relay in Combinatorics
on June 8, 2021.

http://people.maths.ox.ac.uk/scott/relay.htm

  • 2:00 UTC, 11:00 KST Melbourne (Australia) Monash University
    David Wood (Monash University), Universality in Minor-Closed Graph Classes
  • 3:00 UTC, 12:00 KST Shanghai (China) Shanghai Center for Mathematical Sciences
    Baogang Xu (Nanjing Normal University, China), On coloring of graphs of girth 2l+1 without longer odd holes
  • 4:00 UTC, 13:00 KST Auckland (New Zealand) The University of Auckland
    Jeroen Schillewaert (University of Auckland), Constructing highly regular expanders from hyperbolic Coxeter groups
  • 5:00 UTC, 14:00 KST Sydney (Australia) Combinatorial Mathematics Society of Australasia
    Gordon Royle (University of Western Australia (UWA)), Real chromatic roots of planar graphs
  • 6:00 UTC, 15:00 KST Daejeon (Korea) IBS Discrete Mathematics Group
    O-joung Kwon (Incheon National University and IBS Discrete Mathematics Group), Classes of intersection digraphs with good algorithmic properties
  • 7:00 UTC, 16:00 KST Krakow (Poland) Jagiellonian University
    Bartosz Walczak (Jagiellonian), Coloring polygon visibility graphs and their generalizations
  • 8:00 UTC, 17:00 KST Glasgow (UK) University of Glasgow
    Heng Guo (University of Edinburgh), A Markov chain approach towards the sampling Lovász local lemma
  • 9:00 UTC, 18:00 KST London (UK) London School of Economics
    Annika Heckel (LMU), How does the chromatic number of a random graph vary?
  • 10:00 UTC, 19:00 KST Moscow (Russia) Moscow Institute of Physics and Technology
    Noga Alon (Princeton and Tel Aviv)
  • 11:00 UTC, 20:00 KST Budapest (Hungary) Hungarian Academy of Sciences + Eötvös Loránd University
    László Lovász (Eotvos University, Budapest)
  • 12:00 UTC, 21:00 KST Bordeaux (France) LaBRI
    Carla Groenland (Utrecht University), Universal Graphs and Labelling Schemes
  • 13:00 UTC, 22:00 KST New York (USA) City University of New York + Montclair State University + Hofstra University
    Deepak Bal (Montclair State University)
  • 14:00 UTC, 23:00 KST Prague (Czech) Czech Academy of Sciences + Czech Technical University + London School of Economics
    Dhruv Mubayi (University of Illinois at Chicago), The feasible region of hypergraphs
  • 15:00 UTC, 00:00 KST Brno (Czech) Masaryk University
    James Davies (University of Waterloo), Colouring circle graphs and their generalisations
  • 16:00 UTC, 01:00 KST Oxford (UK) University of Oxford
    Jacob Fox (Stanford University), Removal lemmas
  • 17:00 UTC, 02:00 KST Columbus (USA) Ohio State University
    Allan Sly (Princeton University)
  • 18:00 UTC, 03:00 KST Rio (Brazil) Instituto de Matemática Pura e Aplicada
    Marcelo Campos (IMPA), The singularity probability of a random symmetric matrix is exponentially small
  • 19:00 UTC, 04:00 KST Atlanta (USA) Georgia Institute of Technology
    Jim Geelen (University of Waterloo), Homomorphisms and colouring for graphs and binary matroids
  • 20:00 UTC, 05:00 KST Santiago (Chile) Universidad de Chile
    David Conlon (Caltech)
  • 21:00 UTC, 06:00 KST Burnaby (Canada) Simon Fraser University
    Fan Chung (UCSD), Trees and forests in Green’s functions of a graph
  • 22:00 UTC, 07:00 KST Victoria (Canada) University of Victoria
    Andrew Suk (UCSD), Turán-type problems for point-line incidences
  • 23:00 UTC, 08:00 KST Fairbanks (USA) University of Alaska
    Ron Gould (Emory), Chorded cycles

 

Details

Date:
June 8 Tuesday
Time:
3:00 PM - 4:00 PM KST
Event Category:
Event Tags:
,

Venue

Zoom ID: 875 9395 3555 (relay)

Organizer

Sang-il Oum (엄상일)
View Organizer Website
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.