Ouvrir le menu
Publier un document
Alternate Text
clear
fr
Ouvrir le menu
Category Category A New Intersection Model and Improved Algorithms for Tolerance Graphs

A New Intersection Model and Improved Algorithms for Tolerance Graphs

icon

91

pages

icon

English

icon

Documents

Écrit par

Publié par

Lire un extrait
Alternate Text
Lire un extrait
Alternate Text

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

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris
icon

91

pages

icon

English

icon

Ebook

Lire un extrait
Alternate Text
Lire un extrait
Alternate Text

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

Publié par

Nombre de lectures

15

Langue

English

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


Voir Alternate Text

Publié par

Nombre de lectures

15

Langue

English

RWTH Aachen University Sophia Antipolis Open problem Clique (graph theory)
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 vertexv∈Vcan 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|Su∩Sv6=∅}.
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 setSv, such that two vertices ofGare adjacent if and only if the corresponding sets have a nonempty intersection, i.e.E={uv|Su∩Sv6=∅}. Then,F={Sv|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 setSv, such that two vertices ofGare adjacent if and only if the corresponding sets have a nonempty intersection, i.e.E={uv|Su∩Sv6=∅}. Then,F={Sv|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 setSv, such that two vertices ofGare adjacent if and only if the corresponding sets have a nonempty intersection, i.e.E={uv|Su∩Sv6=∅}. Then,F={Sv|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
Voir Alternate Text
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents
Signaler un problème
playstore
appstore
facebook twitter instagram youtube

YouScribe

Le catalogue

Le service

Les conditions

© 2010-2024 YouScribe
Livre audio en ligne - Développement personnel Livre en ligne Tout le catalogue Tous les Intérêts
Alternate Text
Category

Book

Book

icon play
icon play Infos