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
28
29
30
31
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. 2019 (180)
    1. September (7)
    2. August (18)
    3. July (12)
    4. June (23)
    5. May (23)
    6. April (32)
    7. March (25)
    8. February (16)
    9. January (24)
  2. 2018 (221)
    1. December (16)
    2. November (19)
    3. October (26)
    4. September (23)
    5. August (17)
    6. July (20)
    7. June (13)
    8. May (25)
    9. April (34)
    10. March (24)
    11. February (3)
    12. January (1)
  3. 2017 (36)
  4. 2016 (21)
  5. 2015 (36)
  6. 2014 (33)
  7. 2013 (23)
  8. 2012 (4)
  9. 2011 (1)
  10. 2010 (1)
  11. 2009 (1)
  12. 2008 (1)