Ross Churchley (SFU)
06/12/13 12:30 Talks
A survey on monopolar graphs: algorithms and complexity
Speaker:
Ross Churchley (Simon Fraser University, Math.)
Abstract:
A graph is called “monopolar” if its vertices can be partitioned into an independent set and a disjoint union of cliques. It is generally NP-complete to decide whether an given input graph is monopolar. A flurry of papers in the last five years has identified several graph classes (e.g. chordal graphs, line graphs, permutation graphs) where monopolarity can be decided in polynomial time, and others (e.g. planar graphs, triangle-free graphs) where the problem remains NP-complete. This talk will survey these results, show how they can all be derived from observations about a few small structures, and propose new questions for future research.
Date:
Friday, December 6, 2013
Time:
12:30 pm - 1:30 pm
Location:
TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby
Ross Churchley (Simon Fraser University, Math.)
Abstract:
A graph is called “monopolar” if its vertices can be partitioned into an independent set and a disjoint union of cliques. It is generally NP-complete to decide whether an given input graph is monopolar. A flurry of papers in the last five years has identified several graph classes (e.g. chordal graphs, line graphs, permutation graphs) where monopolarity can be decided in polynomial time, and others (e.g. planar graphs, triangle-free graphs) where the problem remains NP-complete. This talk will survey these results, show how they can all be derived from observations about a few small structures, and propose new questions for future research.
Date:
Friday, December 6, 2013
Time:
12:30 pm - 1:30 pm
Location:
TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby