*Coming up the next two weeks (on Zoom)*
*The chapter authors of the recent book*
*Topics in Algorithmic Graph Theory*
Cambridge University Press, 2021,
https://www.cambridge.org/core/books/topics-in-algorithmic-graph-theory/4AD9538A0062A16AC1D53D2BD01A5AF9
* invite you to a pair of talks:*
Nov. 22, 2021 *Dieter Rautenbach *(Ulm, Germany)
Factorially many maximum matchings close to the Erdős-Gallai bound
Nov. 29, 2021 * Celina de Figueiredo* (UFRJ, Brazil)
Maximum cut on interval graphs of interval count four is NP-complete
Time: 7:30 New York; 9:30 Rio and Buenos Aires; 12:30 UK; 13:30 EU;
14:30 Israel; 18:00 India; 21:30 Korea
(Zoom information below)
Feel free to share this announcement to your colleagues and students.
*Here are the details:*
*Title*: * Factorially many maximum matchings close to the Erdős-Gallai
bound *
*Speaker:*
* Dieter Rautenbach (Ulm, Germany) *
*Date: Monday, Nov. 22, 2021 *
*Abstract:* A classical result of Erdős and Gallai determines the maximum
size *m*(*n*,*ν*) of a graph *G* of order *n* and matching number *νn*.
We show that *G* has factorially many maximum matchings provided that its
size is sufficiently close to *m*(*n*,*ν*).
The paper can be found at https://arxiv.org/abs/2108.00134
<https://arxiv.org/abs/2108.00134>
----------------------------
*Title*: * Maximum cut on interval graphs of interval count four is
NP-complete *
*Speaker:** Celina de Figueiredo (UFRJ, Brazil) *
*Date: Monday, Nov. 29, 2021 *
*Abstract:* The computational complexity of the MaxCut problem restricted
to interval graphs has been open since the 80's, being one of the problems
proposed by David Johnson on his Ongoing Guide to NP-completeness, and has
been settled as NP-complete only recently by Adhikary, Bose, Mukherjee and
Roy.
On the other hand, many flawed proofs of polynomiality for MaxCut on the
more restrictive class of unit/proper interval graphs (or graphs with
interval count 1) have been presented along the years, and the
classification of the problem is still not known.
We present the first NP-completeness proof for MaxCut when restricted to
interval graphs with bounded interval count, namely graphs with interval
count 4.
Joint work with Ana Silva, Alexsander Melo and Fabiano Oliveira.
Presented at MFCS 2021.
https://drops.dagstuhl.de/opus/volltexte/2021/14478/pdf/LIPIcs-MFCS-2021-38.pdf
<https://arxiv.org/abs/2108.00134>
*ZOOM INVITATION: The link is below.*
Feel free to pass this on to your colleagues and students.
Looking forward to seeing you on zoom.
============================
*Our REGULAR TIME: *
USA East coast: 7:30
Rio and Buenos Aires: 9:30
UK: 12:30
EU: 13:30
Israel: 14:30
India: 18:00
Korea: 21:30
*The zoom link for this year: *
*Topics in Algorithmic Graph Theory*
Zoom Meeting Link:
https://us06web.zoom.us/j/82694935491?pwd=SW1oYVl2WXJDVTJDUlRISjdjWGcwUT09
Meeting ID: 826 9493 5491
Passcode: 3.14159
If you would like to give a lecture (short or long) or recommend someone
else, feel free to email Martin Golumbic <golumbic@cs.haifa.ac.il>.
Talks can be
(a) Recent research papers and/or work in progress.
(b) Tutorial surveys of topics in algorithmic graph theory.
(c) Proposing and leading a discussion of a paper that we all read.
(d) Updates of your work, and presentations of open questions.
*WE ARE AN INFORMAL GROUP! No pressure -- we love students and postdocs!*
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
