Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 19
Encontrada(s) 1 página(s)

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Web Service SWePT: A Hybrid Opinion Mining Approach

  • Baca-Gomez, Yolanda Raquel
  • Martínez, Alicia
  • Estrada Esquivel, Hugo
  • Hernandez-Farias, Delia Irazu
  • Rosso, Paolo|||0000-0002-8922-1242
[EN] The increasing use of social networks and online sites where people can express their opinions has created a growing interest in Opinion Mining. One of the main tasks of Opinion Mining is to determine whether an opinion is positive or negative. Therefore, the role of the feelings expressed on the web has become crucial, mainly due to the concern of businesses and government to automatically identify the semantic orientation of the views of customers or citizens. This is also a concern, in the area of health to identify psychological disorders. This research focuses on the development of a web application called SWePT (Web Service for Polarity detection in Spanish Texts), which implements the Sequential Minimal Optimization (SMO) algorithm, extracting its features from an affective lexicon in Mexican Spanish. For this purpose, a corpus and an affective lexicon in Mexican Spanish were created. The experiments using three (positive, neutral, negative) and five categories (very positive, positive, neutral, negative, and very negative) allow us to demonstrate the effectiveness of the presented method. SWePT has also been implemented in the Emotion-bracelet interface, which shows the opinion of a user graphically., This work has been partially supported by the Sectorial Fund CONACyT-INEGI: Project with ref. 208471, INFOTEC, Mexico. And, also by the project CNDT-PYR2015-0016, CENIDET, Mexico. The work of the third author was in the framework of the SomEMBED MINECO TIN2015-71147-C2-1-P research project. The National Council for Science and Technology (CONACyT Mexico) has funded the research work of Delia Irazu Hernandez Farias (Grant No. 218109/313683 CVU-369616).
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Dynamic programming for graphs on surfaces

  • Rué Perna, Juan José|||0000-0002-6420-3179
  • Sau, Ignasi
  • Thilikos, Dimitrios
We provide a framework for the design and analysis of dynamic programming algorithms for surface-embedded graphs on n vertices and branchwidth at most k. Our technique applies to general families of problems where standard dynamic programming runs in 2O(k·log k) · n steps. Our approach combines tools from topological graph theory and analytic combinatorics. In particular, we introduce a new type of branch decomposition called surface cut decomposition, generalizing sphere cut decompositions of planar graphs, which has nice combinatorial properties. Namely, the number of partial solutions that can be arranged on a surface cut decomposition can be upper-bounded by the number of noncrossing partitions on surfaces with boundary. It follows that partial solutions can be represented by a single-exponential (in the branchwidth k) number of configurations. This proves that, when applied on surface cut decompositions, dynamic programming runs in 2O(k) · n steps. That way, we considerably extend the class of problems that can be solved in running times with a single-exponential dependence on branchwidth and unify/improve most previous results in this direction.
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Asymptotic enumeration of non-crossing partitions on surfaces

  • Rué Perna, Juan José|||0000-0002-6420-3179
  • Sau, Ignasi
  • Thilikos Touloupas, Dimitrios
We generalize the notion of non-crossing partition on a disk to general surfaces with boundary. For this, we consider a surface S and introduce the number CS(n) of noncrossing partitions of a set of n points laying on the boundary of S
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Dynamic programming for graphs on surfaces

  • Rué Perna, Juan José|||0000-0002-6420-3179
  • Sau, Ignasi
  • Thilikos, Dimitrios
We provide a framework for the design and analysis of dynamic programming algorithms for surface-embedded graphs on n vertices and branchwidth at most k. Our technique applies to general families of problems where standard dynamic programming runs in 2O(k·log k). Our approach combines tools from topological graph theory and analytic combinatorics.
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Outerplanar obstructions for the vertex feedback set

  • Rué Perna, Juan José|||0000-0002-6420-3179
  • Thilikos Touloupas, Dimitrios
  • Stavropoulos, Konstantinos
For k = 1, let Fk be the class of graphs that contains k vertices meeting all its cycles. The minor-obstruction set for Fk is the set obs(Fk) containing all minor-minimal graphs that do not belong to Fk. We denote by Yk the set of all outerplanar graphs in obs(Fk). I
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Bijections for Baxter families and related objects

  • Felsner, Stefan
  • Fusy, Éric
  • Noy Serrano, Marcos|||0000-0002-2399-1359
  • Orden, David
The Baxter number can be written as $B_n = \sum_0^n \Theta_{k,n-k-1}$. These numbers have first appeared in the enumeration of so-called Baxter permutations; $B_n$ is the number of Baxter permutations of size $n$, and $\Theta_{k,l}$ is the number of Baxter permutations with $k$ descents and $l$ rises. With a series of bijections we identify several families of combinatorial objects counted by the numbers $\Theta_{k,l}$. Apart from Baxter permutations, these include plane bipolar orientations with $k+2$ vertices and $l+2$ faces, 2-orientations of planar quadrangulations with $k+2$ white and $l+2$ black vertices, certain pairs of binary trees with $k+1$ left and $l+1$ right leaves, and a family of triples of non-intersecting lattice paths. This last family allows us to determine the value of $\Theta_{k,l}$ as an application of the lemma of Gessel and Viennot. The approach also allows us to count certain other subfamilies, e.g., alternating Baxter permutations, objects with symmetries and, via a bijection with a class of plan bipolar orientations also Schnyder woods of triangulations, which are known to be in bijection with 3-orientations.
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Asymptotic study of subcritical graph classes

  • Drmota, Michael
  • Fusy, Éric
  • Kang, Mihyun
  • Kraus, Veronika
  • Rué Perna, Juan José|||0000-0002-6420-3179
We present a unified general method for the asymptotic study of graphs from the so-called subcritical graph classes, which include the classes of cacti graphs, outerplanar graphs, and series-parallel graphs. This general method works in both the labelled and unlabelled framework. The main results concern the asymptotic enumeration and the limit laws of properties of random graphs chosen from subcritical classes. We show that the number $g_n/n!$ (resp., $g_n$) of labelled (resp., unlabelled) graphs on n vertices from a subcritical graph class ${\mathcal{G}}=\cup_n {\mathcal{G}_n}$ satisfies asymptotically the universal behavior $g_n = c \!n^{-5/2} \!\gamma^n \! (1+o(1))$ for computable constants $c,\gamma$, e.g., $\gamma\approx 9.38527$ for unlabelled series-parallel graphs, and that the number of vertices of degree k (k fixed) in a graph chosen uniformly at random from $\mathcal{G}_n$ converges (after rescaling) to a normal law as $n\to\infty$.
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On the diameter of random planar graphs

  • Chapuy, G.
  • Fusy, Éric
  • Giménez Llach, Omer
  • Noy Serrano, Marcos|||0000-0002-2399-1359
We show that the diameter diam(Gn) of a random labelled connected planar graph with n vertices is equal to n1/4+o(1) , in probability. More precisely, there exists a constant c > 0 such that {equation presented} for ˜ small enough and n = n0(˜). We prove similar statements for 2-connected and 3-connected planar graphs and maps., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Enumeration and limit laws of dissections on a cylinder

  • Rué Perna, Juan José|||0000-0002-6420-3179
We compute the generating function for triangulations on a cylinder, with the restriction that all vertices belong to its boundary and that the intersection of a pair of different faces is either empty, a vertex or an edge. We generalize these results to maps with either constant ({k}-dissections) or unrestricted (unrestricted dissections) face degree. We apply singularity analysis to the resulting generating functions to obtain asymptotic estimates for their coefficients, as well as limit distributions for natural parameters.
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Analytic combinatorics of chord and hyperchord diagrams with k crossings

  • Pilaud, Vincent
  • Rué Perna, Juan José|||0000-0002-6420-3179
Using methods from Analytic Combinatorics, we study the families of perfect matchings, partitions, chord diagrams, and hyperchord diagrams on a disk with a prescribed number of crossings. For each family, we express the generating function of the configurations with exactly k crossings as a rational function of the generating function of crossing-free configurations. Using these expressions, we study the singular behavior of these generating functions and derive asymptotic results on the counting sequences of the configurations with precisely k crossings. Limiting distributions and random generators are also studied.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On the diameter of random planar graphs

  • Chapuy, G.
  • Fusy, Éric
  • Giménez Llach, Omer
  • Noy Serrano, Marcos
We show that the diameter diam(Gn) of a random labelled connected planar graph with n vertices is equal to n1/4+o(1) , in probability. More precisely, there exists a constant c > 0 such that {equation presented} for ˜ small enough and n = n0(˜). We prove similar statements for 2-connected and 3-connected planar graphs and maps., Peer Reviewed, Postprint (author’s final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Asymptotic enumeration of non-crossing partitions on surfaces

  • Rué Perna, Juan José
  • Sau, Ignasi
  • Thilikos Touloupas, Dimitrios
We generalize the notion of non-crossing partition on a disk to general surfaces with boundary. For this, we consider a surface S and introduce the number CS(n) of noncrossing partitions of a set of n points laying on the boundary of S, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Outerplanar obstructions for the vertex feedback set

  • Rué Perna, Juan José
  • Thilikos Touloupas, Dimitrios
  • Stavropoulos, Konstantinos
For k = 1, let Fk be the class of graphs that contains k vertices meeting all its cycles. The minor-obstruction set for Fk is the set obs(Fk) containing all minor-minimal graphs that do not belong to Fk. We denote by Yk the set of all outerplanar graphs in obs(Fk). I, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Enumeration and limit laws of dissections on a cylinder

  • Rué Perna, Juan José
We compute the generating function for triangulations on a cylinder, with the restriction that all vertices belong to its boundary and that the intersection of a pair of different faces is either empty, a vertex or an edge. We generalize these results to maps with either constant ({k}-dissections) or unrestricted (unrestricted dissections) face degree. We apply singularity analysis to the resulting generating functions to obtain asymptotic estimates for their coefficients, as well as limit distributions for natural parameters., Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Bijections for Baxter families and related objects

  • Felsner, Stefan
  • Fusy, Éric
  • Noy Serrano, Marcos
  • Orden, David
The Baxter number can be written as $B_n = \sum_0^n \Theta_{k,n-k-1}$. These numbers have first appeared in the enumeration of so-called Baxter permutations; $B_n$ is the number of Baxter permutations of size $n$, and $\Theta_{k,l}$ is the number of Baxter permutations with $k$ descents and $l$ rises. With a series of bijections we identify several families of combinatorial objects counted by the numbers $\Theta_{k,l}$. Apart from Baxter permutations, these include plane bipolar orientations with $k+2$ vertices and $l+2$ faces, 2-orientations of planar quadrangulations with $k+2$ white and $l+2$ black vertices, certain pairs of binary trees with $k+1$ left and $l+1$ right leaves, and a family of triples of non-intersecting lattice paths. This last family allows us to determine the value of $\Theta_{k,l}$ as an application of the lemma of Gessel and Viennot. The approach also allows us to count certain other subfamilies, e.g., alternating Baxter permutations, objects with symmetries and, via a bijection with a class of plan bipolar orientations also Schnyder woods of triangulations, which are known to be in bijection with 3-orientations., Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Dynamic programming for graphs on surfaces

  • Rué Perna, Juan José
  • Sau, Ignasi
  • Thilikos, Dimitrios
We provide a framework for the design and analysis of dynamic programming algorithms for surface-embedded graphs on n vertices and branchwidth at most k. Our technique applies to general families of problems where standard dynamic programming runs in 2O(k·log k). Our approach combines tools from topological graph theory and analytic combinatorics., Postprint (updated version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Dynamic programming for graphs on surfaces

  • Rué Perna, Juan José
  • Sau, Ignasi
  • Thilikos, Dimitrios
We provide a framework for the design and analysis of dynamic programming algorithms for surface-embedded graphs on n vertices and branchwidth at most k. Our technique applies to general families of problems where standard dynamic programming runs in 2O(k·log k) · n steps. Our approach combines tools from topological graph theory and analytic combinatorics. In particular, we introduce a new type of branch decomposition called surface cut decomposition, generalizing sphere cut decompositions of planar graphs, which has nice combinatorial properties. Namely, the number of partial solutions that can be arranged on a surface cut decomposition can be upper-bounded by the number of noncrossing partitions on surfaces with boundary. It follows that partial solutions can be represented by a single-exponential (in the branchwidth k) number of configurations. This proves that, when applied on surface cut decompositions, dynamic programming runs in 2O(k) · n steps. That way, we considerably extend the class of problems that can be solved in running times with a single-exponential dependence on branchwidth and unify/improve most previous results in this direction., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Analytic combinatorics of chord and hyperchord diagrams with k crossings

  • Pilaud, Vincent
  • Rué Perna, Juan José
Using methods from Analytic Combinatorics, we study the families of perfect matchings, partitions, chord diagrams, and hyperchord diagrams on a disk with a prescribed number of crossings. For each family, we express the generating function of the configurations with exactly k crossings as a rational function of the generating function of crossing-free configurations. Using these expressions, we study the singular behavior of these generating functions and derive asymptotic results on the counting sequences of the configurations with precisely k crossings. Limiting distributions and random generators are also studied., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Asymptotic study of subcritical graph classes

  • Drmota, Michael
  • Fusy, Éric
  • Kang, Mihyun
  • Kraus, Veronika
  • Rué Perna, Juan José
We present a unified general method for the asymptotic study of graphs from the so-called subcritical graph classes, which include the classes of cacti graphs, outerplanar graphs, and series-parallel graphs. This general method works in both the labelled and unlabelled framework. The main results concern the asymptotic enumeration and the limit laws of properties of random graphs chosen from subcritical classes. We show that the number $g_n/n!$ (resp., $g_n$) of labelled (resp., unlabelled) graphs on n vertices from a subcritical graph class ${\mathcal{G}}=\cup_n {\mathcal{G}_n}$ satisfies asymptotically the universal behavior $g_n = c \!n^{-5/2} \!\gamma^n \! (1+o(1))$ for computable constants $c,\gamma$, e.g., $\gamma\approx 9.38527$ for unlabelled series-parallel graphs, and that the number of vertices of degree k (k fixed) in a graph chosen uniformly at random from $\mathcal{G}_n$ converges (after rescaling) to a normal law as $n\to\infty$., Postprint (updated version)