Skip to main content

Resultados relacionados

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

UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

FPT algorithms for plane completion problems

  • Chatzidimitriou, Dimitris
  • Giannopoulou, Archontia C.
  • Maniatis, Spyridon
  • Requile, Clement|||0000-0002-7689-7972
  • Thilikos, Dimitrios M.
  • Zoros, Dimitris
The Plane Subgraph (resp. Topological Minor) Completion problem asks, given a (possibly disconnected) plane (multi)graph Gamma and a connected plane (multi)graph Delta, whether it is possible to add edges in Gamma without violating the planarity of its embedding so that it contains some subgraph (resp. topological minor) that is topologically isomorphic to Delta. We give FPT algorithms that solve both problems in f(|E(Delta)|)*|E(\Gamma)|^{2} steps. Moreover, for the Plane Subgraph Completion problem we show that f(k)=2^{O(k*log(k))}., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Subgraph statistics in subcritical graph classes

  • Drmota, Michael
  • Ramos Garrido, Lander
  • Rué Perna, Juan José|||0000-0002-6420-3179
Let H be a fixed graph and math formula a subcritical graph class. In this paper we show that the number of occurrences of H (as a subgraph) in a graph in math formula of order n, chosen uniformly at random, follows a normal limiting distribution with linear expectation and variance. The main ingredient in our proof is the analytic framework developed by Drmota, Gittenberger and Morgenbesser to deal with infinite systems of functional equations [Drmota, Gittenberger, and Morgenbesser, Submitted]. As a case study, we obtain explicit expressions for the number of triangles and cycles of length 4 in the family of series-parallel graphs.
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

On the limiting distribution of the metric dimension for random forests

  • Rué Perna, Juan José|||0000-0002-6420-3179
  • Mitsche, Dieter
The metric dimension of a graph G is the minimum size of a subset S of vertices of G such that all other vertices are uniquely determined by their distances to the vertices in S. In this paper we investigate the metric dimension for two different models of random forests, in each case obtaining normal limit distributions for this parameter.
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Many 2-level polytopes from matroids

  • Grande, Francesco
  • Rué Perna, Juan José|||0000-0002-6420-3179
The final publication is available at Springer via DOI 10.1007/s00454-015-9735-5, The family of 2-level matroids, that is, matroids whose base polytope is 2-level, has been recently studied and characterized by means of combinatorial properties. 2-Level matroids generalize series-parallel graphs, which have been already successfully analyzed from the enumerative perspective. We bring to light some structural properties of 2-level matroids and exploit them for enumerative purposes. Moreover, the counting results are used to show that the number of combinatorially non-equivalent (n-1)(n-1)-dimensional 2-level polytopes is bounded from below by c·n-5/2·¿-nc·n-5/2·¿-n, where c˜0.03791727c˜0.03791727 and ¿-1˜4.88052854¿-1˜4.88052854.
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Maximal independent sets and maximal matchings in series-parallel and related graph classes

  • Drmota, Michael
  • Ramos Garrido, Lander
  • Requilé, Clément
  • Rué Perna, Juan José|||0000-0002-6420-3179
The goal of this paper is to obtain quantitative results on the number and on the size of maximal independent sets and maximal matchings in several block-stable graph classes that satisfy a proper sub-criticality condition. In particular we cover trees, cacti graphs and seriesparallel graphs. The proof methods are based on a generating function approach and a proper singularity analysis of solutions of implicit systems of functional equations in several variables. As a byproduct, this method extends previous results of Meir and Moon for trees [Meir, Moon: On maximal independent sets of nodes in trees, Journal of Graph Theory 1988].
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Spanning trees in random series-parallel graphs

  • Rué Perna, Juan José|||0000-0002-6420-3179
  • Ehrenmüller, Julia
By means of analytic techniques we show that the expected number of spanning trees in a connected labelled series-parallel graph on n vertices chosen uniformly at random satisfies an estimate of the form s%-n(1 + o(1)), where s and % are computable constants, the values of which are approximately s ˜ 0.09063 and %-1 ˜ 2.08415. We obtain analogue results for subfamilies of series-parallel graphs including 2-connected series-parallel graphs, 2-trees, and series-parallel graphs with fixed excess.
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Counting configuration–free sets in groups

  • Rué Perna, Juan José|||0000-0002-6420-3179
  • Serra Albó, Oriol|||0000-0001-8561-4631
  • Vena Cros, Lluís|||0000-0002-0075-3673
We present a unified framework to asymptotically count the number of sets, with a given cardinality, free of certain configurations. This is done by combining the hypergraph containers methodology joint with arithmetic removal lemmas. Several applications involving linear configurations are described, as well as some applications in the random sparse setting.
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Maximal independent sets and maximal matchings in series-parallel and related graph classes

  • Drmota, Michael
  • Ramos, Lander
  • Requilé, Clément
  • Rué Perna, Juan José|||0000-0002-6420-3179
We provide combinatorial decompositions as well as asymptotic tight estimates for two maximal parameters: the number and average size of maximal independent sets and maximal matchings in seriesparallel graphs (and related graph classes) with n vertices. In particular, our results extend previous results of Meir and Moon for trees [Meir, Moon: On maximal independent sets of nodes in trees, Journal of Graph Theory 1988]. We also show that these two parameters converge to a central limit law.
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Counting configuration-free sets in groups

  • Rué Perna, Juan José|||0000-0002-6420-3179
  • Serra Albó, Oriol|||0000-0001-8561-4631
  • Vena Cros, Lluís|||0000-0002-0075-3673
© 2017 Elsevier Ltd. We provide asymptotic counting for the number of subsets of given size which are free of certain configurations in finite groups. Applications include sets without solutions to equations in non-abelian groups, and linear configurations in abelian groups defined from group homomorphisms. The results are obtained by combining the methodology of hypergraph containers joint with arithmetic removal lemmas. Random sparse versions and threshold probabilities for existence of configurations in sets of given density are presented as well.
UPCommons. Portal del coneixement obert de la UPC
Publication 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
Publication Artículo científico (JournalArticle)

On the limiting distribution of the metric dimension for random forests

  • Rué Perna, Juan José
  • Mitsche, Dieter
The metric dimension of a graph G is the minimum size of a subset S of vertices of G such that all other vertices are uniquely determined by their distances to the vertices in S. In this paper we investigate the metric dimension for two different models of random forests, in each case obtaining normal limit distributions for this parameter., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Counting configuration-free sets in groups

  • Rué Perna, Juan José
  • Serra Albó, Oriol
  • Vena Cros, Lluís
© 2017 Elsevier Ltd. We provide asymptotic counting for the number of subsets of given size which are free of certain configurations in finite groups. Applications include sets without solutions to equations in non-abelian groups, and linear configurations in abelian groups defined from group homomorphisms. The results are obtained by combining the methodology of hypergraph containers joint with arithmetic removal lemmas. Random sparse versions and threshold probabilities for existence of configurations in sets of given density are presented as well., Postprint (updated version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Spanning trees in random series-parallel graphs

  • Rué Perna, Juan José
  • Ehrenmüller, Julia
By means of analytic techniques we show that the expected number of spanning trees in a connected labelled series-parallel graph on n vertices chosen uniformly at random satisfies an estimate of the form s%-n(1 + o(1)), where s and % are computable constants, the values of which are approximately s ˜ 0.09063 and %-1 ˜ 2.08415. We obtain analogue results for subfamilies of series-parallel graphs including 2-connected series-parallel graphs, 2-trees, and series-parallel graphs with fixed excess., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

FPT algorithms for plane completion problems

  • Chatzidimitriou, Dimitris
  • Giannopoulou, Archontia C.
  • Maniatis, Spyridon
  • Requile, Clement
  • Thilikos, Dimitrios M.
  • Zoros, Dimitris
The Plane Subgraph (resp. Topological Minor) Completion problem asks, given a (possibly disconnected) plane (multi)graph Gamma and a connected plane (multi)graph Delta, whether it is possible to add edges in Gamma without violating the planarity of its embedding so that it contains some subgraph (resp. topological minor) that is topologically isomorphic to Delta. We give FPT algorithms that solve both problems in f(|E(Delta)|)*|E(\Gamma)|^{2} steps. Moreover, for the Plane Subgraph Completion problem we show that f(k)=2^{O(k*log(k))}., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Counting configuration–free sets in groups

  • Rué Perna, Juan José
  • Serra Albó, Oriol
  • Vena Cros, Lluís
We present a unified framework to asymptotically count the number of sets, with a given cardinality, free of certain configurations. This is done by combining the hypergraph containers methodology joint with arithmetic removal lemmas. Several applications involving linear configurations are described, as well as some applications in the random sparse setting., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Subgraph statistics in subcritical graph classes

  • Drmota, Michael
  • Ramos Garrido, Lander
  • Rué Perna, Juan José
Let H be a fixed graph and math formula a subcritical graph class. In this paper we show that the number of occurrences of H (as a subgraph) in a graph in math formula of order n, chosen uniformly at random, follows a normal limiting distribution with linear expectation and variance. The main ingredient in our proof is the analytic framework developed by Drmota, Gittenberger and Morgenbesser to deal with infinite systems of functional equations [Drmota, Gittenberger, and Morgenbesser, Submitted]. As a case study, we obtain explicit expressions for the number of triangles and cycles of length 4 in the family of series-parallel graphs., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Maximal independent sets and maximal matchings in series-parallel and related graph classes

  • Drmota, Michael
  • Ramos, Lander
  • Requilé, Clément
  • Rué Perna, Juan José
We provide combinatorial decompositions as well as asymptotic tight estimates for two maximal parameters: the number and average size of maximal independent sets and maximal matchings in seriesparallel graphs (and related graph classes) with n vertices. In particular, our results extend previous results of Meir and Moon for trees [Meir, Moon: On maximal independent sets of nodes in trees, Journal of Graph Theory 1988]. We also show that these two parameters converge to a central limit law., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Maximal independent sets and maximal matchings in series-parallel and related graph classes

  • Drmota, Michael
  • Ramos Garrido, Lander
  • Requilé, Clément
  • Rué Perna, Juan José
The goal of this paper is to obtain quantitative results on the number and on the size of maximal independent sets and maximal matchings in several block-stable graph classes that satisfy a proper sub-criticality condition. In particular we cover trees, cacti graphs and seriesparallel graphs. The proof methods are based on a generating function approach and a proper singularity analysis of solutions of implicit systems of functional equations in several variables. As a byproduct, this method extends previous results of Meir and Moon for trees [Meir, Moon: On maximal independent sets of nodes in trees, Journal of Graph Theory 1988]., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Many 2-level polytopes from matroids

  • Grande, Francesco
  • Rué Perna, Juan José
The final publication is available at Springer via DOI 10.1007/s00454-015-9735-5, The family of 2-level matroids, that is, matroids whose base polytope is 2-level, has been recently studied and characterized by means of combinatorial properties. 2-Level matroids generalize series-parallel graphs, which have been already successfully analyzed from the enumerative perspective. We bring to light some structural properties of 2-level matroids and exploit them for enumerative purposes. Moreover, the counting results are used to show that the number of combinatorially non-equivalent (n-1)(n-1)-dimensional 2-level polytopes is bounded from below by c·n-5/2·¿-nc·n-5/2·¿-n, where c˜0.03791727c˜0.03791727 and ¿-1˜4.88052854¿-1˜4.88052854., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication 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)