Algorítmica y complejidad computacional. Recopilación de enlaces marzo 2017.

    1. Desde hoy mismo he empezado a ver de nuevo a diario algunas categorías de Arxiv. A continuación algunos artículos que he visto. También otros artículos no necesariamente de Arxiv. Ordenados por orden de interés.
    2. Cayley graphs on groups with commutator subgroup of order 2p are hamiltonian. Dave Witte Morris Department of Mathematics and Computer Science, University of Lethbridge, Lethbridge, Alberta, T1K 3M4, Canada Abstract. We show that if G is a finite group whose commutator subgroup [G,G] has order 2p, where p is an odd prime, then every connected Cayley graph on G has a hamiltonian cycle. Leyendolo, aunque se refiere a Grafos de Cayley, que nos interesan menos. En la introducción se resume muy claramente el resultado: Let G be a finite group. It is easy to show that if G is abelian (and |G| > 2), then every connected Cayley graph on G has a hamiltonian cycle. (See Definition 2.1 for the definition of the term Cayley graph.) To generalize this observation, one can try to prove the same conclusion for groups that are close to being abelian. Since a group is abelian precisely when its commutator subgroup is trivial, it is therefore natural to try to find a hamiltonian cycle when the commutator subgroup of G is close to being trivial. The following theorem, which was proved in a series of papers, is a well-known result along these lines. Theorem 1.1 (Marusiˇ c [ ˇ 13], Durnberger [4, 5], 1983–1985). If the commutator subgroup [G,G] of G has prime order, then every connected Cayley graph on G has a hamiltonian cycle. D. Marusiˇ c (personal communication) suggested more than thirty years ago that it ˇ should be possible to replace the prime with a product pq of two distinct primes: Research Problem 1.2 (D. Marusiˇ c, personal communication, 1985) ˇ . Show that if the commutator subgroup of G has order pq, where p and q are two distinct primes, then every connected Cayley graph on G has a hamiltonian cycle. This has recently been accomplished when G is either nilpotent [8] or of odd order [14]. As another step toward the solution of this problem, we establish the special case where q = 2: Theorem 1.3. If the commutator subgroup of G has order 2p, where p is an odd prime, then every connected Cayley graph on G has a hamiltonian cycle. See the bibliography of [12] for references to other results on hamiltonian cycles in Cayley graphs. Relacionado: la página de wkipedia sobre commutator subgroup. Extracto: The commutator subgroup of the symmetric group Sn is the alternating group An. Obviamente An no entrará, ni en general ni en particular, dentro del resultado de este artículo.
    3. A CONJECTURE ON DETERMINING WHICH (n, k)-STAR GRAPHS ARE NOT CAYLEY GRAPHS KARIMAH SWEET, LI LI, EDDIE CHENG, LASZL ´ O LIPT ´ AK, AND DANIEL STEFFY ´ Abstract. In this paper, we continue the work begun by Cheng et al. on classifying which of the (n, k)-star graphs are Cayley. We present a conjecture for the complete classification, and prove an asymptotic version of the conjecture, that is, the conjecture is true for all k ≥ 2 when n is sufficiently large. For k = 2, . . . , 15 we prove that the conjecture is true for all n ≥ k + 2 (with the possible exception of S17,14). The proof reveals some unexpected connection between (n, k)-star graphs and the classification of multiply transitive groups (which is closely related to the classification of finite simple groups).
    4. Graph Theory and Interconnection NetworksEscrito por Lih-Hsing Hsu,Cheng-Kuan Lin. He visto este libro en la bibliografía. Para mi sorpresa gran parte del contenido de este libro de 2009 trata de recorridos hamiltonianos. Pese a la sorpresa, seguramente ya lo hemos enlazado en alguna que otra ocasión.

    5. Nonexistence of Efficient Dominating Sets in the Cayley Graphs Generated by Transposition Trees of Diameter 3 Italo J. Dejter University of Puerto Rico Rio Piedras, PR 00936-8377 e-mail: Abstract Let Xd n be a Cayley graph generated by a transposition tree of diameter d. It is known that every V (Xd n) = Sn with d < 3 splits into efficient dominating sets. However, no X3 n has efficient dominating sets, shown in this work along related developments.
    6. Una familia de grafos que  no conocía: los I-Graphs. Un poco de historia: In 1950 a class of generalized Petersen graphs was introduced by Coxeter and around 1970 popularized by Frucht, Graver and Watkins. The family of I-graphs mentioned in 1988 by Bouwer et al. represents a slight further albeit important generalization of the renowned Petersen graph….I-graphs were introduced in the Foster census [5] and form a natural generalization of the generalized Petersen graphs introduced by Coxeter [8] and named by Watkins [26] .  Relacionado. 

      Lovrečič Saražin, M. “A Note on the Generalized Petersen Graphs That Are Also Cayley Graphs.” J. Combin. Th. B 69, 226-229, 1997.

      Nedela, R. and Škoviera, M. “Which Generalized Petersen Graphs Are Cayley Graphs?” J. Graph Th. 19, 1-11, 1995.

    7. Symmetric powers of permutation representations of finite groups and primitive colorings on polyhedrons Tomoyuki Tamura Graduate school of Mathematics Kyushu University 2017 Abstract In this paper1 , we define a set which has a finite group action and is generated by a finite color set, a set which has a finite group action, and a subset of the set of non negative integers. we state its properties to apply one of solution of the following two problems, respectively. First, we calculate the generating function of the character of symmetric powers of permutation representation associated with a set which has a finite group action. Second, we calculate the number of primitive colorings on some objects of polyhedrons. It is a generalization of the calculation of the number of primitive necklaces by N.Metropolis and G-C.Rota.. Probablemente sin interés para nuestro  tema. 
    8. The Unconstrained Binary Quadratic Programming Problem: A Survey. Este es el problema para el que está optimizada la máquina de D-wave. UBQP = QUBO es el problema al que se deben de reducir los problemas tratables por D-Wave. En el artículo siguiente relacionado comentan que esta reducción (una instancia de subgraph isomorphism) podría ser un “cuello de botella”, en el sentido en el que comentábamos en la anterior entrada. Por mucho que tu máquina funcione instántaneamente, si para construir el input con el que va a trabajar tienes que resolver un problema exponencial en el peor caso, mal vas. Matar moscas a cañonazos. Luego matizan y es posible que  los  input para la máquina de D-Wave eviten este problema. También es posible que sean entonces inputs sencillos en cualquier caso, que admitan resolución por algoritmo polinómico clásico. Según leí en los blogs a los que enlacé ayer, por ahí van los tiros. In order to solve a problem, D-Wave needs it to be first translated into a QUBO.  This QUBO in turns needs to be transformed into an Ising spin glass into their machine.  To cut  along story short, it means that the QUBO problem must be mapped onto a special graph, called a chimera graph


  1. Internet of Things: An Overview Farzad Khodadadi, Amir Vahid Dastjerdi, and Rajkumar Buyya Abstract As technology proceeds and the number of smart devices continues to grow substantially, need for ubiquitous context-aware platforms that support interconnected, heterogeneous, and distributed network of devices has given rise to what is referred today as Internet-ofThings. However, paving the path for achieving aforementioned objectives and making the IoT paradigm more tangible requires integration and convergence of different knowledge and research domains, covering aspects from identification and communication to resource discovery and service integration. Through this chapter, we aim to highlight researches in topics including proposed architectures, security and privacy, network communication means and protocols, and eventually conclude by providing future directions and open challenges facing the IoT development. He visto este artículo en la categoría de paralelismo. Me ha sorprendido verlo ahí (también muchos otros). A ver si me entero que sobre que va este tema. Prioridad cero. Relacionado. 1. J. Bradley, J. Barbier, and D. Handler, “Embracing the internet of everything to capture your share of $14.4 trillion,” 2014. [Online]. Available: us/about/ac79/docs/innov/IoE Economy.pdf 2. J. Manyika, M. Chui, P. Bisson, J. Woetzel, R. Dobbs, J. Bughin, and D. Aharon. (2015, June) Unlocking the potential of the internet of things. McKinsey Global Institute. [Online]. 22 Shuo Chen et al. Available: our-insights/the-internet-of-things-the-value-of-digitizing-the-physical-world 3. (2014, Jan) Cisco delivers vision of fog computing to accelerate value from billions of connected devices. Cisco. Press release. [Online]. Available:


2 comentarios to “Algorítmica y complejidad computacional. Recopilación de enlaces marzo 2017.”

  1. Says:

    Hallo, Ich finde den Aufbau der Seite super.

    Macht bitte weiter so.

  2. Clarinda Says:

    I’ll try to put this to good use imtemiadely.

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de

Estás comentando usando tu cuenta de Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )


Conectando a %s

A %d blogueros les gusta esto: