Succinct encodings of graphs and other combinatorial structures
Considerem el següent problema. Donada una família de grafs amb un cert nombre de grafs amb n vèrtexs, volem trobar una representació per a qualsevol graf dins la família fent servir un nombre òptim de bits. És a dir, sigui t el nombre de grafs amb n vèrtexs a la família, volem codificar qualsevol d...
| Autor: | |
|---|---|
| Tipo de documento: | Tesis de maestría |
| Fecha de publicación: | 2023 |
| País: | España |
| Institución: | Universitat Politècnica de Catalunya (UPC) |
| Repositorio: | UPCommons. Portal del coneixement obert de la UPC |
| Lenguaje: | Inglés |
| OAI Identifier: | oai:upcommons.upc.edu:2117/398207 |
| Acceso en línea: | https://hdl.handle.net/2117/398207 |
| Nivel de acceso: | Acceso abierto |
| Palabra clave: | Trees (Graph theory) succinct graph encoding tree graphs graphs with small separators recursive graph encoding Arbres (Teoria de grafs) Classificació AMS::05 Combinatorics::05C Graph theory Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs |
| _version_ | 1878742295349559296 |
|---|---|
| author | Lumbreras Navarro, Raúl |
| author_browse | Lumbreras Navarro, Raúl |
| author_facet | Lumbreras Navarro, Raúl |
| author_role | author |
| collection | UPCommons. Portal del coneixement obert de la UPC |
| description | Considerem el següent problema. Donada una família de grafs amb un cert nombre de grafs amb n vèrtexs, volem trobar una representació per a qualsevol graf dins la família fent servir un nombre òptim de bits. És a dir, sigui t el nombre de grafs amb n vèrtexs a la família, volem codificar qualsevol d'aquests grafs fent servir log(t) + o(log(t)) bits, que és el mínim necessari asimptòticament. El primer tipus de famílies que considerem per codificar són diferents tipus de famílies d'arbres, per exemple, arbres ordenats, arbres k-aris i arbres no ordenats. Expliquem dos mètodes per codificar famílies d'arbres. El primer és per a famílies específiques d'arbres i el segon és per a famílies generals d'arbres. A continuació, també considerem les famílies més generals de grafs que siguin tancades per subgrafs induïts i que tinguin separadors petits. Aquestes famílies inclouen grafs planars i qualsevol família de grafs tancada per menors. També presentem una aplicació detallada d'aquesta codificació. |
| eu_rights_str_mv | openAccess |
| format | masterThesis |
| id | ES_f36456e99b8c02a95bc5c8de4be1254e |
| institution | Universitat Politècnica de Catalunya (UPC) |
| instname_str | Universitat Politècnica de Catalunya (UPC) |
| language | eng |
| network_acronym_str | ES |
| network_name_str | España |
| oai_identifier_str | oai:upcommons.upc.edu:2117/398207 |
| publishDate | 2023 |
| publishDateSort | 2023 |
| publisher | Universitat Politècnica de Catalunya |
| publisherStr | Universitat Politècnica de Catalunya |
| reponame_str | UPCommons. Portal del coneixement obert de la UPC |
| spelling | Succinct encodings of graphs and other combinatorial structures Lumbreras Navarro, Raúl Trees (Graph theory) succinct graph encoding tree graphs graphs with small separators recursive graph encoding Arbres (Teoria de grafs) Classificació AMS::05 Combinatorics::05C Graph theory Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs Considerem el següent problema. Donada una família de grafs amb un cert nombre de grafs amb n vèrtexs, volem trobar una representació per a qualsevol graf dins la família fent servir un nombre òptim de bits. És a dir, sigui t el nombre de grafs amb n vèrtexs a la família, volem codificar qualsevol d'aquests grafs fent servir log(t) + o(log(t)) bits, que és el mínim necessari asimptòticament. El primer tipus de famílies que considerem per codificar són diferents tipus de famílies d'arbres, per exemple, arbres ordenats, arbres k-aris i arbres no ordenats. Expliquem dos mètodes per codificar famílies d'arbres. El primer és per a famílies específiques d'arbres i el segon és per a famílies generals d'arbres. A continuació, també considerem les famílies més generals de grafs que siguin tancades per subgrafs induïts i que tinguin separadors petits. Aquestes famílies inclouen grafs planars i qualsevol família de grafs tancada per menors. També presentem una aplicació detallada d'aquesta codificació. Consideramos el siguiente problema. Dada una familia de grafos con un cierto número de grafos de n vértices, queremos encontrar una representación para cualquier grafo dentro de la familia utilizando un número de bits optimo. Es decir, sea t el número de grafos de n vértices en la familia, queremos codificar cualquiera de dichos grafos usando log(t) + o(log(t)) bits, que es el mínimo necesario asintóticamente. El primer tipo de familias que consideramos codificar son distintos tipos de familias de árboles, por ejemplo, árboles ordenados, árboles k-arios y árboles no ordenados. Explicamos dos métodos para codificar familias de árboles. El primero es para familias específicas de árboles y el segundo es para familias generales de árboles. A continuación, también consideramos las familias más generales de grafos que son cerradas por subgrafos inducidos y tienen separadores pequeños. Estas familias incluyen grafos planares y cualquier familia de grafos cerrada por menores. También presentamos una aplicación detallada de esta codificación. We consider the following problem. Given a family of graphs with a certain number of n-vertex graphs, we want to find a representation for any graph within the family using an information-theoretical number of bits. That is to say, if there are a certain number of n-vertex graphs t in the family, then, we want to encode any of such graphs using log(t) + o(log(t)) bits, which is the asymptotically minimum needed. The first type of families we consider encoding are different types of tree families, for instance, ordered trees, k-ary trees and unordered trees. We explain two methods for encoding such families. The first one for specific families of trees and the second one for general families of trees. Then, we also consider the more general families of graphs which are closed under induced sub-graphs and have small separators. These families include planar graphs and any minor-closed family of graphs. We also present a detailed implementation of such encoding. Universitat Politècnica de Catalunya https://hdl.handle.net/2117/398207 |
| spellingShingle | Succinct encodings of graphs and other combinatorial structures Lumbreras Navarro, Raúl Trees (Graph theory) succinct graph encoding tree graphs graphs with small separators recursive graph encoding Arbres (Teoria de grafs) Classificació AMS::05 Combinatorics::05C Graph theory Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs |
| title | Succinct encodings of graphs and other combinatorial structures |
| title_full | Succinct encodings of graphs and other combinatorial structures |
| title_fullStr | Succinct encodings of graphs and other combinatorial structures |
| title_full_unstemmed | Succinct encodings of graphs and other combinatorial structures |
| title_short | Succinct encodings of graphs and other combinatorial structures |
| title_sort | Succinct encodings of graphs and other combinatorial structures |
| topic | Trees (Graph theory) succinct graph encoding tree graphs graphs with small separators recursive graph encoding Arbres (Teoria de grafs) Classificació AMS::05 Combinatorics::05C Graph theory Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs |
| topic_facet | Trees (Graph theory) succinct graph encoding tree graphs graphs with small separators recursive graph encoding Arbres (Teoria de grafs) Classificació AMS::05 Combinatorics::05C Graph theory Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs |
| url | https://hdl.handle.net/2117/398207 |