Pasar al contenido principal

Resultados relacionados

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

UPCommons. Portal del coneixement obert de la UPC
Publicación 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
Publicación 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
Publicación 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.
Recercat. Dipósit de la Recerca de Catalunya
Publicación 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
Publicación 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
Publicación 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)