A New Intersection Model and Improved Algorithms for Tolerance Graphs

George Mertzios

Description

A New Intersection Model and Improved Algorithms for Tolerance Graphs George B. Mertzios1 Ignasi Sau2 Shmuel Zaks3 1RWTH Aachen University, Germany 2INRIA/CNRS/UNSA, Sophia-Antipolis, France UPC, Barcelona, Spain 3Technion, Haifa, Israel WG 2009 George Mertzios (RWTH Aachen Univ.) An Intersection Model for Tolerance Graphs WG 2009 1 / 26

• tolerance graphs


• sophia antipolis


• shmuel zaks3


• su ?


• mertzios1 ignasi


• minimum coloring


• intersection model


• lemma every


• open problems


• maximum clique

Sujets

• RWTH Aachen University
• Sophia Antipolis
• Open problem
• Clique (graph theory)

Informations

• Publié par: pefav
• Nombre de lectures: 15
• Langue: English

Extrait

A

New

George Mertzios

Model and Improved Tolerance Graphs

Intersection for

George B. Mertzios 1 Ignasi Sau 2 Shmuel Zaks 3

1 RWTH Aachen University, Germany

2 INRIA/CNRS/UNSA, Sophia-Antipolis, France UPC, Barcelona, Spain

(RWTH Aachen Univ.)

3 Technion, Haifa, Israel

WG 2009

An Intersection Model for Tolerance Graphs

Algorithms

WG 2009

1 / 26

A

New

George Mertzios

Intersection for

Model and Improved Tolerance Graphs

George B. Mertzios 1 Ignasi Sau 2 Shmuel Zaks 3

1 RWTH Aachen University, Germany

2 INRIA/CNRS/UNSA, Sophia-Antipolis, France UPC, Barcelona, Spain

(RWTH Aachen Univ.)

3 Technion, Haifa, Israel

WG 2009

An Intersection Model for Tolerance Graphs

Algorithms

WG 2009

1 / 26

Overview

Preliminaries on tolerance graphs.

A new intersection model.

A canonical representation and applications of this model.

Minimum Coloring:O(nlogn)(optimal) [previous result:O(n 2 )].

Maximum Clique:aO(nlogn)(optimal) [previous result:O(n 2 )].

Maximum Weighted Independent Set:O(n 2 )[previous result:O(n 3 )].

Open problems.

George Mertzios (RWTH Aachen Univ.)

An Intersection Model for Tolerance Graphs

WG 2009

2 / 26

Intersection graphs

Definition An undirected graphG= (V,E)is called anintersection graph, if each vertexv∈Vcan be assigned to a setS v , such that two vertices ofGare adjacent if and only if the corresponding sets have a nonempty intersection, i.e.E={uv|S u ∩S v 6=∅}.

George Mertzios (RWTH Aachen Univ.)

An Intersection Model for Tolerance Graphs

WG 2009

3 / 26

Intersection graphs

Definition An undirected graphG= (V,E)is called anintersection graph, if each vertexv∈Vcan be assigned to a setS v , such that two vertices ofGare adjacent if and only if the corresponding sets have a nonempty intersection, i.e.E={uv|S u ∩S v 6=∅}. Then,F={S v |v∈V}is theintersection modelofG.

George Mertzios (RWTH Aachen Univ.)

An Intersection Model for Tolerance Graphs

WG 2009

3 / 26

Intersection graphs

Definition An undirected graphG= (V,E)is called anintersection graph, if each vertexv∈Vcan be assigned to a setS v , such that two vertices ofGare adjacent if and only if the corresponding sets have a nonempty intersection, i.e.E={uv|S u ∩S v 6=∅}. Then,F={S v |v∈V}is theintersection modelofG.

George Mertzios (RWTH Aachen Univ.)

An Intersection Model for Tolerance Graphs

WG 2009

3 / 26

Intersection graphs

Definition An undirected graphG= (V,E)is called anintersection graph, if each vertexv∈Vcan be assigned to a setS v , such that two vertices ofGare adjacent if and only if the corresponding sets have a nonempty intersection, i.e.E={uv|S u ∩S v 6=∅}. Then,F={S v |v∈V}is theintersection modelofG.

Lemma Every undirected graph G adjacency relations.

George Mertzios (RWTH Aachen Univ.)

has a (trivial) intersection model, based on

An Intersection Model for Tolerance Graphs

WG 2009

3 / 26

Interval and permutation graphs

Definition A graphGis called aninterval graph, ifGis the intersection graph of a set of intervals on the real line.

George Mertzios (RWTH Aachen Univ.)

An Intersection Model for Tolerance Graphs

WG 2009

4 / 26

Interval and permutation graphs

Definition A graphGis called aninterval graph, ifGis the intersection graph of a set of intervals on the real line.

Definition A graphGis called apermutation graph, ifGis the intersection graph of a set of line segments between two parallel lines.

George Mertzios (RWTH Aachen Univ.)

An Intersection Model for Tolerance Graphs

WG 2009

4 / 26