A New Intersection Model and Improved Algorithms for Tolerance Graphs
91 pages
English

A New Intersection Model and Improved Algorithms for Tolerance Graphs

-

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
91 pages
English
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

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

Informations

Publié par
Nombre de lectures 15
Langue English

Exrait

A
New
George Mertzios
Model and Improved Tolerance Graphs
Intersection for
George B. Mertzios1Ignasi Sau2 Shmuel Zaks3
1RWTH Aachen University, Germany
2INRIA/CNRS/UNSA, Sophia-Antipolis, France UPC, Barcelona, Spain
(RWTH Aachen Univ.)
3Technion, 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. Mertzios1Ignasi Sau2 Shmuel Zaks3
1RWTH Aachen University, Germany
2INRIA/CNRS/UNSA, Sophia-Antipolis, France UPC, Barcelona, Spain
(RWTH Aachen Univ.)
3Technion, 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(n2)].
Maximum Clique:aO(nlogn)(optimal) [previous result:O(n2)].
Maximum Weighted Independent Set:O(n2)[previous result:O(n3)].
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 vertexvVcan be assigned to a setSv, such that two vertices ofGare adjacent if and only if the corresponding sets have a nonempty intersection, i.e.E={uv|SuSv6=}.
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 vertexvVcan be assigned to a setSv, such that two vertices ofGare adjacent if and only if the corresponding sets have a nonempty intersection, i.e.E={uv|SuSv6=}. Then,F={Sv|vV}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 vertexvVcan be assigned to a setSv, such that two vertices ofGare adjacent if and only if the corresponding sets have a nonempty intersection, i.e.E={uv|SuSv6=}. Then,F={Sv|vV}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 vertexvVcan be assigned to a setSv, such that two vertices ofGare adjacent if and only if the corresponding sets have a nonempty intersection, i.e.E={uv|SuSv6=}. Then,F={Sv|vV}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
  • Accueil Accueil
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • BD BD
  • Documents Documents