University of Waterloo COVID-19 update

The University of Waterloo is constantly updating its most frequently asked questions.

Questions about buildings and services? Please visit the list of modified services.

Please note: The University of Waterloo is closed for all events until further notice.

PhD Seminar • Algorithms and Complexity — Cutwidth, Imbalance, and the Structure of Optimal OrderingsExport this event to calendar

Wednesday, July 10, 2019 — 1:30 PM EDT

Jan Gorzny, PhD candidate
David R. Cheriton School of Computer Science

We show that both Cutwidth and Imbalance are fixed-parameter tractable when parameterized by the twin-cover number of the input graph. We further show that Imbalance is NP-complete for split graphs and linear-time solvable for proper interval (bipartite) graphs, which equals the complexity of Cutwidth on these classes. Both results follow from a new structural theorem, that every instance of Cutwidth or Imbalance has an optimal ordering of a restricted form. This is joint work with Jonathan Buss.

Location 
DC - William G. Davis Computer Research Centre
1304
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
  1. 2020 (74)
    1. May (3)
    2. April (7)
    3. March (17)
    4. February (25)
    5. January (22)
  2. 2019 (255)
    1. December (21)
    2. November (25)
    3. October (16)
    4. September (20)
    5. August (18)
    6. July (12)
    7. June (23)
    8. May (23)
    9. April (32)
    10. March (25)
    11. February (16)
    12. January (24)
  3. 2018 (220)
  4. 2017 (36)
  5. 2016 (21)
  6. 2015 (36)
  7. 2014 (33)
  8. 2013 (23)
  9. 2012 (4)
  10. 2011 (1)
  11. 2010 (1)
  12. 2009 (1)
  13. 2008 (1)