<?xml version="1.0" encoding="UTF-8"?>
 <rdf:RDF xmlns="http://purl.org/rss/1.0/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:taxo="http://purl.org/rss/1.0/modules/taxonomy/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:cc="http://web.resource.org/cc/" xmlns:syn="http://purl.org/rss/1.0/modules/syndication/" xmlns:admin="http://webns.net/mvcb/">
  <channel rdf:about="http://pinboard.in">
    <title>Pinboard (Vaguery)</title>
    <link>https://pinboard.in/u:Vaguery/public/</link>
    <description>recent bookmarks from Vaguery</description>
    <items>
      <rdf:Seq>	<rdf:li rdf:resource="https://arxiv.org/abs/2405.17629"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2212.01987"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2412.04607"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2011.04195"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2403.17969"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2406.14153"/>
	<rdf:li rdf:resource="https://hal.science/hal-04710512v1"/>
	<rdf:li rdf:resource="https://occupymath.wordpress.com/2021/01/14/graph-domination-a-mathematical-game/"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2212.11644"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2110.14237"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2308.08868"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2209.14775"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2304.07217"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2308.08970"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2110.07972"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2205.13202"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2102.02321"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2106.14856"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1811.08181"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1709.02990"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2201.04888"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1905.04490"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2002.07087"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2010.15770"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1808.05689"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2106.14402"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2010.11448"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2109.15069"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1704.06467"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1605.02713"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2111.02992"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2011.02735"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1612.07276"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1803.03468"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1903.01805"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1901.07842"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1512.02381"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1603.08974"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2010.05518"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2101.12560"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2105.06150"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1902.10752"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1802.06478"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2102.05738"/>
	<rdf:li rdf:resource="https://github.com/simongray/clojure-graph-resources#datalog"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2002.04025"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2104.14863"/>
	<rdf:li rdf:resource="https://www.youtube.com/channel/UC6j-G6oPmkqCgOx6UQOUhSQ"/>
	<rdf:li rdf:resource="https://imaginary.org/snapshot/limits-of-graph-sequences"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1912.05251"/>
	<rdf:li rdf:resource="https://www.quantamagazine.org/a-new-algorithm-for-graph-crossings-hiding-in-plain-sight-20200915/"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1911.03449"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1605.08640"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1704.07067"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1607.07426"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1703.10293"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1909.03152"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2002.06421"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1506.04380"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2004.13491"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1904.08746"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1705.01595"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1604.01282"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1610.02107"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1804.02075"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1904.04341"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1710.08486"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/math/0608422"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1904.05269"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1903.06012"/>
      </rdf:Seq>
    </items>
  </channel><item rdf:about="https://arxiv.org/abs/2405.17629">
    <title>[2405.17629] Lindenmayer graph languages, first-order theories and expanders</title>
    <dc:date>2026-05-25T11:55:14+00:00</dc:date>
    <link>https://arxiv.org/abs/2405.17629</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Combinatorial generation of expander families and Lindenmayer-style development models are both parallel in nature. Both can be handled within proposed parallel graph grammar formalism. Their first-order properties can then be checked by encompassing the generated graph language into an appropriate automatic structure.
]]></description>
<dc:subject>L-systems rewriting-systems graph-theory grammars automata to-write-about review</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:10b55460d8ee/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:L-systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rewriting-systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:grammars"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:automata"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:review"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2212.01987">
    <title>[2212.01987] Fractal dimensions for Iterated Graph Systems</title>
    <dc:date>2025-12-01T15:45:37+00:00</dc:date>
    <link>https://arxiv.org/abs/2212.01987</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Building upon [1], this study aims to introduce fractal geometry into graph theory, and to establish a potential theoretical foundation for complex networks. Specifically, we employ the method of substitution to create and explore fractal-like graphs, termed deterministic or random iterated graph systems. While the concept of substitution is commonplace in fractal geometry and dynamical systems, its analysis in the context of graph theory remains a nascent field.
By delving into the properties of these systems, including diameter and distal, we derive two primary outcomes. Firstly, within the deterministic iterated graph systems, we establish that the Minkowski dimension and Hausdorff dimension align analytically through explicit formulae. Secondly, in the case of random iterated graph systems, we demonstrate that almost every graph limit exhibits identical Minkowski and Hausdorff dimensions numerically by their Lyapunov exponents.
The exploration of iterated graph systems holds the potential to unveil novel directions. These findings not only, mathematically, contribute to our understanding of the interplay between fractals and graphs, but also, physically, suggest promising avenues for applications for complex networks.
]]></description>
<dc:subject>rewriting-systems graph-theory graph-grammars rather-interesting fractals to-understand consider:L-systems consider:MAP-L-systems</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:75a61bc1a3c6/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rewriting-systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-grammars"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:fractals"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:L-systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:MAP-L-systems"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2412.04607">
    <title>[2412.04607] Asymptotics of the partial $n$-fold dimer model</title>
    <dc:date>2025-08-22T12:57:42+00:00</dc:date>
    <link>https://arxiv.org/abs/2412.04607</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We study a model of colored multiwebs, which generalizes the dimer model to allow each vertex to be adjacent to nv edges. These objects can be formulated as a random tiling of a graph with partial dimer covers. We examine the case of a cycle graph, and in particular we describe the local correlations of tiles in this setting.
]]></description>
<dc:subject>graph-theory enumeration counting looking-to-see rather-interesting constraint-satisfaction to-simulate</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:8f18f8e19396/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:enumeration"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:counting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:constraint-satisfaction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2011.04195">
    <title>[2011.04195] Stack-number is not bounded by queue-number</title>
    <dc:date>2025-08-22T12:55:15+00:00</dc:date>
    <link>https://arxiv.org/abs/2011.04195</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We describe a family of graphs with queue-number at most 4 but unbounded stack-number. This resolves open problems of Heath, Leighton and Rosenberg (1992) and Blankenship and Oporowski (1999).
]]></description>
<dc:subject>graph-theory feature-construction rather-interesting looking-to-see to-write-about to-simulate consider:visualization</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:d6313da823d4/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:visualization"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2403.17969">
    <title>[2403.17969] Antimagic Labeling of Graphs Using Prime Numbers</title>
    <dc:date>2025-04-16T18:54:29+00:00</dc:date>
    <link>https://arxiv.org/abs/2403.17969</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Graph labeling is a technique that assigns unique labels or weights to the vertices or edges of a graph, often used to analyze and solve various graph-related problems. There are few methods with certain limitations conducted by researchers previously on this topic. This research paper focuses on antimagic labeling of different types of graphs and trees. It entails the assignment of distinct prime values to edges in a manner that ensures the cumulative sum of edge labels at each vertex remains unique. This research proposes a conjecture on antimagic labeling of any graphs and proves two theories. Firstly, we tried to give weights to the edges randomly, as some exceptions are faced in particular phases in this way, we followed a whole new way to mitigate this problem. This research paper demonstrates computational and mathematical verification to prove that antimagic labeling of any perfect binary tree and complete graph is possible.
]]></description>
<dc:subject>mathematical-recreations graph-theory number-theory constraint-satisfaction rather-interesting to-write-about consider:simulation consider:heuristics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:da0ed41493e0/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematical-recreations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:number-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:constraint-satisfaction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:simulation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:heuristics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2406.14153">
    <title>[2406.14153] On random classical marginal problems with applications to quantum information theory</title>
    <dc:date>2025-04-05T21:58:13+00:00</dc:date>
    <link>https://arxiv.org/abs/2406.14153</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[In this paper, we study random instances of the classical marginal problem. We encode the problem in a graph, where the vertices have assigned fixed binary probability distributions, and edges have assigned random bivariate distributions having the incident vertex distributions as marginals. We provide estimates on the probability that a joint distribution on the graph exists, having the bivariate edge distributions as marginals. Our study is motivated by Fine's theorem in quantum mechanics. We study in great detail the graphs corresponding to CHSH and Bell-Wigner scenarios providing rations of volumes between the local and non-signaling polytopes.
]]></description>
<dc:subject>quantum-computing probability-theory to-understand graph-theory looking-to-see estimation marginal-problems</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:d7576cf56f42/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:quantum-computing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:probability-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:estimation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:marginal-problems"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://hal.science/hal-04710512v1">
    <title>The Harmonious Coloring Game - Archive ouverte HAL</title>
    <dc:date>2024-10-05T14:09:10+00:00</dc:date>
    <link>https://hal.science/hal-04710512v1</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[A harmonious k-coloring of a graph G is a 2-distance proper k-coloring of its vertices such that each edge is uniquely identified by the colors of its endpoints. Here, we introduce its game version: the harmonious coloring game. In this two-player game, Alice and Bob alternately select an uncolored vertex and assigns to it a color in {1, . . . , k} with the constraint that, at every turn, the set of colored vertices induces a valid partial harmonious coloring. Alice wins if all vertices are colored; otherwise, Bob wins. The harmonious game chromatic number χ hg (G) is the minimum integer k such that Alice has a winning strategy with k colors. In this paper, we prove the PSPACE-hardness of three variants of this game. As a by-product, we prove that a variant introduced by Chen et al. in 1997 of the classical graph coloring game is PSPACE-hard. We also obtain lower and upper bounds for χ hg (G) in graph classes, such as paths, cycles, grids and forests of stars.

]]></description>
<dc:subject>graph-theory mathematical-recreations game-theory rather-interesting computational-complexity to-write-about to-simulate consider:looking-to-see consider:random-sampling consider:performance-measures</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:0ecde86680b1/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematical-recreations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:game-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:random-sampling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:performance-measures"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://occupymath.wordpress.com/2021/01/14/graph-domination-a-mathematical-game/">
    <title>Graph Domination – A Mathematical Game – Occupy Math</title>
    <dc:date>2024-10-05T12:40:05+00:00</dc:date>
    <link>https://occupymath.wordpress.com/2021/01/14/graph-domination-a-mathematical-game/</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[This post introduces a game we created a few years back for use in outreach. It takes about five minutes to learn to play, tops, but the game has interesting strategy — some of which can be discovered by just playing. In fact, the trick of blocking an opponent’s entry point is one several students discovered spontaneously and with some delight. Graph domination is also played on boards that are simple enough that the people participating in your outreach activity can make their own. In fact “make up your own board” is one of the possible activities. The materials needed are the board and some tokens in two colors or types. The game illustrates the concept of domination from graph theory. Readers familiar with war games will recognize “domination” as covering some of the same issues that are covered by zones of control.

]]></description>
<dc:subject>mathematical-recreations graph-theory games to-write-about</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:a4c614d82829/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mathematical-recreations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:games"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2212.11644">
    <title>[2212.11644] Poset Matrix Structure Via Partial Composition Operations</title>
    <dc:date>2024-09-05T01:03:26+00:00</dc:date>
    <link>https://arxiv.org/abs/2212.11644</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[This paper examines the structure of poset matrices by formulating a set of new construction rules for this purpose. In this direction, the technique of partial composition operation will be introduced as the basis for the construction of poset matrices of any given size by extending the combinatorial setting of species of structures to poset matrices. More specifically, three new partial composition operations that apply to poset matrices are defined as the foundation for this study. Several new structural properties derived from viewing any poset matrix and its dual in terms of these operations are highlighted.
]]></description>
<dc:subject>sorting combinatorics graph-theory matrices construction rather-interesting to-understand enumeration consider:lexicase consider:multiobjective-sets consider:probability-theory</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:0d7d0ee327b3/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:sorting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:enumeration"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:lexicase"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:multiobjective-sets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:probability-theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2110.14237">
    <title>[2110.14237] Learning Graph Cellular Automata</title>
    <dc:date>2024-08-08T13:37:36+00:00</dc:date>
    <link>https://arxiv.org/abs/2110.14237</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Cellular automata (CA) are a class of computational models that exhibit rich dynamics emerging from the local interaction of cells arranged in a regular lattice. In this work we focus on a generalised version of typical CA, called graph cellular automata (GCA), in which the lattice structure is replaced by an arbitrary graph. In particular, we extend previous work that used convolutional neural networks to learn the transition rule of conventional CA and we use graph neural networks to learn a variety of transition rules for GCA. First, we present a general-purpose architecture for learning GCA, and we show that it can represent any arbitrary GCA with finite and discrete state space. Then, we test our approach on three different tasks: 1) learning the transition rule of a GCA on a Voronoi tessellation; 2) imitating the behaviour of a group of flocking agents; 3) learning a rule that converges to a desired target state.
]]></description>
<dc:subject>cellular-automata artificial-life engineering-design rather-interesting graph-theory to-understand to-simulate consider:graph-algorithms consider:distributed-computing consider:ReQ</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:457fe2d84025/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:cellular-automata"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:artificial-life"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:engineering-design"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:graph-algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:distributed-computing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:ReQ"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2308.08868">
    <title>[2308.08868] Computing complexity measures of degenerate graphs</title>
    <dc:date>2024-04-01T11:33:55+00:00</dc:date>
    <link>https://arxiv.org/abs/2308.08868</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We show that the VC-dimension of a graph can be computed in time nlogd+1dO(d), where d is the degeneracy of the input graph. The core idea of our algorithm is a data structure to efficiently query the number of vertices that see a specific subset of vertices inside of a (small) query set. The construction of this data structure takes time O(d2dn), afterwards queries can be computed efficiently using fast Möbius inversion.
This data structure turns out to be useful for a range of tasks, especially for finding bipartite patterns in degenerate graphs, and we outline an efficient algorithms for counting the number of times specific patterns occur in a graph. The largest factor in the running time of this algorithm is O(nc), where c is a parameter of the pattern we call its left covering number.
Concrete applications of this algorithm include counting the number of (non-induced) bicliques in linear time, the number of co-matchings in quadratic time, as well as a constant-factor approximation of the ladder index in linear time.
Finally, we supplement our theoretical results with several implementations and run experiments on more than 200 real-world datasets -- the largest of which has 8 million edges -- where we obtain interesting insights into the VC-dimension of real-world networks.
]]></description>
<dc:subject>computational-complexity graph-theory algorithms horse-races rather-interesting looking-to-see to-write-about consider:evolved consider:stress-testing</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:368bb27f15be/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:horse-races"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:evolved"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:stress-testing"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2209.14775">
    <title>[2209.14775] On Constructing Spanners from Random Gaussian Projections</title>
    <dc:date>2023-10-12T11:11:56+00:00</dc:date>
    <link>https://arxiv.org/abs/2209.14775</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Graph sketching is a powerful paradigm for analyzing graph structure via linear measurements introduced by Ahn, Guha, and McGregor (SODA'12) that has since found numerous applications in streaming, distributed computing, and massively parallel algorithms, among others. Graph sketching has proven to be quite successful for various problems such as connectivity, minimum spanning trees, edge or vertex connectivity, and cut or spectral sparsifiers. Yet, the problem of approximating shortest path metric of a graph, and specifically computing a spanner, is notably missing from the list of successes. This has turned the status of this fundamental problem into one of the most longstanding open questions in this area.
We present a partial explanation of this lack of success by proving a strong lower bound for a large family of graph sketching algorithms that encompasses prior work on spanners and many (but importantly not also all) related cut-based problems mentioned above. Our lower bound matches the algorithmic bounds of the recent result of Filtser, Kapralov, and Nouri (SODA'21), up to lower order terms, for constructing spanners via the same graph sketching family. This establishes near-optimality of these bounds, at least restricted to this family of graph sketching techniques, and makes progress on a conjecture posed in this latter work.
]]></description>
<dc:subject>graph-theory numerical-methods matrices rather-interesting linear-projection transformations heuristics to-understand to-write-about</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:82ddc5bf2751/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:numerical-methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:linear-projection"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:transformations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:heuristics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2304.07217">
    <title>[2304.07217] Distinguishing graphs by their spectra, Smith normal forms and complements</title>
    <dc:date>2023-08-24T12:52:04+00:00</dc:date>
    <link>https://arxiv.org/abs/2304.07217</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[The search for a highly discriminating and easily computable invariant to distinguish graphs remains a challenging research topic. Here we focus on cospectral graphs whose complements are also cospectral (generalized cospectral), and on coinvariant graphs (same Smith normal form) whose complements are also coinvariant (generalized coinvariant). We show a new characterization of generalized cospectral graphs in terms of codeterminantal graphs. We also establish the Smith normal form of some graph classes for certain associated matrices, and as an application, we prove that the Smith normal form can be used to uniquely determine star graphs. Finally, for graphs up to 10 vertices, we present enumeration results on the number of generalized cospectral graphs and generalized coinvariant graphs with respect to several associated matrices.
]]></description>
<dc:subject>graph-theory classification rather-interesting feature-construction discriminators to-write-about nudge-targets consider:feature-discovery</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:c5b5f63237fe/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:classification"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discriminators"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:feature-discovery"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2308.08970">
    <title>[2308.08970] Geodetic Graphs: Experiments and New Constructions</title>
    <dc:date>2023-08-22T13:23:48+00:00</dc:date>
    <link>https://arxiv.org/abs/2308.08970</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[In 1962 Ore initiated the study of geodetic graphs. A graph is called geodetic if the shortest path between every pair of vertices is unique. In the subsequent years a wide range of papers appeared investigating their peculiar properties. Yet, a complete classification of geodetic graphs is out of reach. 
In this work we present a program enumerating all geodetic graphs of a given size. Using our program, we succeed to find all geodetic graphs with up to 25 vertices and all regular geodetic graphs with up to 32 vertices. This leads to the discovery of two new infinite families of geodetic graphs.
]]></description>
<dc:subject>graph-theory classification rather-interesting generative-models enumeration combinatorics nudge-targets consider:classification to-write-about</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:74624b80c3f9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:classification"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:generative-models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:enumeration"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:classification"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2110.07972">
    <title>[2110.07972] Exploring the infinitesimal rigidity of planar configurations of points and rods</title>
    <dc:date>2023-04-30T00:42:33+00:00</dc:date>
    <link>https://arxiv.org/abs/2110.07972</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[This article is concerned with the rigidity properties of geometric realizations of incidence geometries of rank two as points and lines in the Euclidean plane; we care about the distance being preserved among collinear points. We discuss the rigidity properties of geometric realizations of incidence geometries in relation to the rigidity of geometric realizations of other well-known structures, such as graphs and hypergraphs.The 2-plane matroid is also discussed. 
Further, we extend a result of Whiteley to determine necessary conditions for an incidence geometry of points and lines with exactly three points on each line, or 3-uniform hypergraphs, to have a minimally rigid realization as points and lines in the plane. We also give examples to show that these conditions are not sufficient. 
Finally, we examine the rigidity properties of vk-configurations. We provide several examples of rigid v3-configurations, and families of flexible geometric v3-configurations. The exposition of the material is supported by many figures.
]]></description>
<dc:subject>graph-theory mechanical-linkages rigidity rather-interesting constraint-satisfaction optimization minimal-structures to-understand</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:3341984cec46/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:mechanical-linkages"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rigidity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:constraint-satisfaction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:minimal-structures"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2205.13202">
    <title>[2205.13202] More Recent Advances in (Hyper)Graph Partitioning</title>
    <dc:date>2023-04-12T13:06:24+00:00</dc:date>
    <link>https://arxiv.org/abs/2205.13202</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[In recent years, significant advances have been made in the design and evaluation of balanced (hyper)graph partitioning algorithms. We survey trends of the last decade in practical algorithms for balanced (hyper)graph partitioning together with future research directions. Our work serves as an update to a previous survey on the topic. In particular, the survey extends the previous survey by also covering hypergraph partitioning and streaming algorithms, and has an additional focus on parallel algorithms.
]]></description>
<dc:subject>hypergraphs graph-theory algorithms computational-complexity rather-interesting</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:aa408bec37d3/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:hypergraphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2102.02321">
    <title>[2102.02321] Hamiltonicity of graphs perturbed by a random geometric graph</title>
    <dc:date>2022-04-15T14:11:08+00:00</dc:date>
    <link>https://arxiv.org/abs/2102.02321</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We study Hamiltonicity in graphs obtained as the union of a deterministic n-vertex graph H with linear degrees and a d-dimensional random geometric graph Gd(n,r), for any d≥1. We obtain an asymptotically optimal bound on the minimum r for which a.a.s. H∪Gd(n,r) is Hamiltonian. Our proof provides a linear time algorithm to find a Hamilton cycle in such graphs.
]]></description>
<dc:subject>graph-theory perturbations robustness rather-interesting looking-to-see experiment to-write-about to-simulate consider:visualization</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:84e39663a356/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:perturbations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:robustness"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:experiment"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:visualization"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2106.14856">
    <title>[2106.14856] Farey-subgraphs and Continued Fractions</title>
    <dc:date>2022-04-09T12:08:36+00:00</dc:date>
    <link>https://arxiv.org/abs/2106.14856</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[In this note, we study a family of subgraphs of the Farey graph, denoted as N for every N∈ℕ. 
We show that N is connected if and only if N is either equal to one or a prime power. We introduce a class of continued fractions referred to as N-continued fractions for each N>1. We establish a relation between N-continued fractions and certain paths from infinity in the graph N. We discuss existence and uniqueness of N-continued fraction expansions of real numbers.
]]></description>
<dc:subject>continued-fractions number-theory representation to-understand visualization graph-theory</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:54d565c3f70a/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:continued-fractions"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:number-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:visualization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1811.08181">
    <title>[1811.08181] HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings</title>
    <dc:date>2022-03-19T12:05:49+00:00</dc:date>
    <link>https://arxiv.org/abs/1811.08181</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[To cope with the intractability of answering Conjunctive Queries (CQs) and solving Constraint Satisfaction Problems (CSPs), several notions of hypergraph decompositions have been proposed -- giving rise to different notions of width, noticeably, plain, generalized, and fractional hypertree width (hw, ghw, and fhw). Given the increasing interest in using such decomposition methods in practice, a publicly accessible repository of decomposition software, as well as a large set of benchmarks, and a web-accessible workbench for inserting, analysing, and retrieving hypergraphs are called for. 
We address this need by providing (i) concrete implementations of hypergraph decompositions (including new practical algorithms), (ii) a new, comprehensive benchmark of hypergraphs stemming from disparate CQ and CSP collections, and (iii) HyperBench, our new web-inter\-face for accessing the benchmark and the results of our analyses. In addition, we describe a number of actual experiments we carried out with this new infrastructure.
]]></description>
<dc:subject>constraint-satisfaction hypergraphs graph-theory feature-construction to-understand looking-to-see sampling rather-interesting</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:7a376b8111cd/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:constraint-satisfaction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:hypergraphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:sampling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1709.02990">
    <title>[1709.02990] Large monochromatic components and long monochromatic cycles in random hypergraphs</title>
    <dc:date>2022-03-15T15:51:26+00:00</dc:date>
    <link>https://arxiv.org/abs/1709.02990</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We extend results of Gyárfás and Füredi on the largest monochromatic component in r-colored complete k-uniform hypergraphs to the setting of random hypergraphs. We also study long monochromatic loose cycles in r-colored random hypergraphs. In particular, we obtain a random analog of a result of Gyárfás, Sárközy, and Szemerédi on the longest monochromatic loose cycle in 2-colored complete k-uniform hypergraphs.
]]></description>
<dc:subject>hypergraphs graph-theory algorithms graph-coloring computational-complexity to-understand to-write-about to-visualize</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:c45ed0ef1df5/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:hypergraphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-coloring"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-visualize"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2201.04888">
    <title>[2201.04888] Generating graphs randomly</title>
    <dc:date>2022-03-12T13:08:54+00:00</dc:date>
    <link>https://arxiv.org/abs/2201.04888</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Graphs are used in many disciplines to model the relationships that exist between objects in a complex discrete system. Researchers may wish to compare a network of interest to a "typical" graph from a family (or ensemble) of graphs which are similar in some way. One way to do this is to take a sample of several random graphs from the family, to gather information about what is "typical". Hence there is a need for algorithms which can generate graphs uniformly (or approximately uniformly) at random from the given family. Since a large sample may be required, the algorithm should also be computationally efficient. 
Rigorous analysis of such algorithms is often challenging, involving both combinatorial and probabilistic arguments. We will focus mainly on the set of all simple graphs with a particular degree sequence, and describe several different algorithms for sampling graphs from this family uniformly, or almost uniformly.
]]></description>
<dc:subject>review graph-theory random-graphs rather-interesting algorithms combinatorics sampling to-write-about to-visualize</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:10e6ca326168/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:review"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:random-graphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:sampling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-visualize"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1905.04490">
    <title>[1905.04490] Triangle-creation processes on cubic graphs</title>
    <dc:date>2022-03-12T13:04:45+00:00</dc:date>
    <link>https://arxiv.org/abs/1905.04490</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[An edge switch is an operation which makes a local change in a graph while maintaining the degree of every vertex. We introduce a switch move, called a triangle switch, which creates or deletes at least one triangle. Specifically, a make move is a triangle switch which chooses a path zwvxy of length 4 and replaces it by a triangle vxwv and an edge yz, while a break move performs the reverse operation. We consider various Markov chains which perform random triangle switches, and assume that every possible make or break move has positive probability of being performed. 
Our first result is that any such Markov chain is irreducible on the set of all 3-regular graphs with vertex set {1,2,…,n}. For a particular, natural Markov chain of this type, 
we obtain a non-trivial linear upper and lower bounds on the number of triangles in the long run. These bounds are almost surely obtained in linear time, irrespective of the starting graph.
]]></description>
<dc:subject>graph-theory rewriting-systems rather-interesting combinatorics random-graphs network-theory to-understand to-write-about to-simulate</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:e077ff5346e5/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rewriting-systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:random-graphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:network-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2002.07087">
    <title>[2002.07087] Graph Deconvolutional Generation</title>
    <dc:date>2022-02-17T11:13:59+00:00</dc:date>
    <link>https://arxiv.org/abs/2002.07087</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Graph generation is an extremely important task, as graphs are found throughout different areas of science and engineering. In this work, we focus on the modern equivalent of the Erdos-Renyi random graph model: the graph variational autoencoder (GVAE). This model assumes edges and nodes are independent in order to generate entire graphs at a time using a multi-layer perceptron decoder. As a result of these assumptions, GVAE has difficulty matching the training distribution and relies on an expensive graph matching procedure. We improve this class of models by building a message passing neural network into GVAE's encoder and decoder. We demonstrate our model on the specific task of generating small organic molecules
]]></description>
<dc:subject>graph-theory representation neural-networks generative-models constraint-satisfaction rather-interesting to-understand consider:code-generation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:28d788816c3a/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:neural-networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:generative-models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:constraint-satisfaction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:code-generation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2010.15770">
    <title>[2010.15770] Recursive Random Contraction Revisited</title>
    <dc:date>2022-02-17T11:10:28+00:00</dc:date>
    <link>https://arxiv.org/abs/2010.15770</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[In this note, we revisit the recursive random contraction algorithm of Karger and Stein for finding a minimum cut in a graph. Our revisit is occasioned by a paper of Fox, Panigrahi, and Zhang which gives an extension of the Karger-Stein algorithm to minimum cuts and minimum k-cuts in hypergraphs. When specialized to the case of graphs, the algorithm is somewhat different than the original Karger-Stein algorithm. We show that the analysis becomes particularly clean in this case: we can prove that the probability that a fixed minimum cut in an n node graph is returned by the algorithm is bounded below by 1/(2Hn−2), where Hn is the nth harmonic number. We also consider other similar variants of the algorithm, and show that no such algorithm can achieve an asymptotically better probability of finding a fixed minimum cut.
]]></description>
<dc:subject>graph-theory algorithms hypergraphs computational-complexity to-simulate to-visualize</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:56b524ee82bd/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:hypergraphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-visualize"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1808.05689">
    <title>[1808.05689] SimGNN: A Neural Network Approach to Fast Graph Similarity Computation</title>
    <dc:date>2022-02-13T12:34:52+00:00</dc:date>
    <link>https://arxiv.org/abs/1808.05689</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Graph similarity search is among the most important graph-based applications, e.g. finding the chemical compounds that are most similar to a query compound. Graph similarity computation, such as Graph Edit Distance (GED) and Maximum Common Subgraph (MCS), is the core operation of graph similarity search and many other applications, but very costly to compute in practice. Inspired by the recent success of neural network approaches to several graph applications, such as node or graph classification, we propose a novel neural network based approach to address this classic yet challenging graph problem, aiming to alleviate the computational burden while preserving a good performance. 
The proposed approach, called SimGNN, combines two strategies. First, we design a learnable embedding function that maps every graph into a vector, which provides a global summary of a graph. A novel attention mechanism is proposed to emphasize the important nodes with respect to a specific similarity metric. Second, we design a pairwise node comparison method to supplement the graph-level embeddings with fine-grained node-level information. Our model achieves better generalization on unseen graphs, and in the worst case runs in quadratic time with respect to the number of nodes in two graphs. Taking GED computation as an example, experimental results on three real graph datasets demonstrate the effectiveness and efficiency of our approach. Specifically, our model achieves smaller error rate and great time reduction compared against a series of baselines, including several approximation algorithms on GED computation, and many existing graph neural network based models. To the best of our knowledge, we are among the first to adopt neural networks to explicitly model the similarity between two graphs, and provide a new direction for future research on graph similarity computation and graph similarity search.
]]></description>
<dc:subject>graph-theory distance metrics rather-interesting neural-networks classification clustering to-understand to-write-about consider:code-metrics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:30ad3e377134/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:distance"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:metrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:neural-networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:classification"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:code-metrics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2106.14402">
    <title>[2106.14402] Combinatorial BLAS 2.0: Scaling combinatorial algorithms on distributed-memory systems</title>
    <dc:date>2022-02-05T13:38:08+00:00</dc:date>
    <link>https://arxiv.org/abs/2106.14402</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Combinatorial algorithms such as those that arise in graph analysis, modeling of discrete systems, bioinformatics, and chemistry, are often hard to parallelize. The Combinatorial BLAS library implements key computational primitives for rapid development of combinatorial algorithms in distributed-memory systems. During the decade since its first introduction, the Combinatorial BLAS library has evolved and expanded significantly. 
This paper details many of the key technical features of Combinatorial BLAS version 2.0, such as communication avoidance, hierarchical parallelism via in-node multithreading, accelerator support via GPU kernels, generalized semiring support, implementations of key data structures and functions, and scalable distributed I/O operations for human-readable files. Our paper also presents several rules of thumb for choosing the right data structures and functions in Combinatorial BLAS 2.0, under various common application scenarios.
]]></description>
<dc:subject>distributed-processing linear-algebra algorithms rather-interesting to-understand graph-theory optimization</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:43b6a59343f0/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:distributed-processing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:linear-algebra"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:optimization"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2010.11448">
    <title>[2010.11448] Parallel Algorithms and Heuristics for Efficient Computation of High-Order Line Graphs of Hypergraphs</title>
    <dc:date>2022-02-01T12:14:36+00:00</dc:date>
    <link>https://arxiv.org/abs/2010.11448</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[This paper considers structures of systems beyond dyadic (pairwise) interactions and investigates mathematical modeling of multi-way interactions and connections as hypergraphs, where captured relationships among system entities are set-valued. To date, in most situations, entities in a hypergraph are considered connected as long as there is at least one common "neighbor". However, minimal commonality sometimes discards the "strength" of connections and interactions among groups. To this end, considering the "width" of a connection, referred to as the s-overlap of neighbors, provides more meaningful insights into how closely the communities or entities interact with each other. In addition, s-overlap computation is the fundamental kernel to construct the line graph of a hypergraph, a low-order approximation of the hypergraph which can carry significant information about the original hypergraph. Subsequent stages of a data analytics pipeline then can apply highly-tuned graph algorithms on the line graph to reveal important features. Given a hypergraph, computing the s-overlaps by exhaustively considering all pairwise entities can be computationally prohibitive. To tackle this challenge, we develop efficient algorithms to compute s-overlaps and the corresponding line graph of a hypergraph. We propose several heuristics to avoid execution of redundant work and improve performance of the s-overlap computation. Our parallel algorithm, combined with these heuristics, is orders of magnitude (more than 10×) faster than the naive algorithm in all cases and the SpGEMM algorithm with filtration in most cases (especially with large s value).
]]></description>
<dc:subject>hypergraphs graph-theory algorithms rather-interesting computational-complexity consider:the-thing-rather-than-the-method</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:b4e033a7becf/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:hypergraphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:the-thing-rather-than-the-method"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2109.15069">
    <title>[2109.15069] $K$-selective percolation: A simple model leading to a rich repertoire of phase transitions</title>
    <dc:date>2022-01-26T13:40:08+00:00</dc:date>
    <link>https://arxiv.org/abs/2109.15069</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We propose the K-selective percolation process as a model for the iterative removals of nodes with the specific intermediate degree in complex networks. In the model, a random node with degree K is deactivated one by one until no more nodes with degree K remain. The non-monotonic response of the giant component size on various synthetic and real-world networks implies a conclusion that a network can be more robust against such selective attack by removing further edges. In the theoretical perspective, the K-selective percolation process exhibits a rich repertoire of phase transitions, including double transitions of hybrid and continuous, as well as reentrant transitions. Notably, we observe a tricritical-like point on Erdős-Rényi networks. We also examine a discontinuous transition with unusual order parameter fluctuation and distribution on simple cubic lattices, which does not appear in other percolation models with cascade processes. Finally, we perform finite-size scaling analysis to obtain critical exponents on various transition points, including those exotic ones.
]]></description>
<dc:subject>network-theory graph-theory feature-construction rather-interesting robustness algorithms numerical-methods to-write-about to-simulate consider:inverse-problem consider:weird-maxima percolation phase-transitions</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:4c1fae0a3809/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:network-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:robustness"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:numerical-methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:inverse-problem"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:weird-maxima"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:percolation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:phase-transitions"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1704.06467">
    <title>[1704.06467] Visibility graphs and symbolic dynamics</title>
    <dc:date>2022-01-26T13:37:04+00:00</dc:date>
    <link>https://arxiv.org/abs/1704.06467</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Visibility algorithms are a family of geometric and ordering criteria by which a real-valued time series of N data is mapped into a graph of N nodes. This graph has been shown to often inherit in its topology non-trivial properties of the series structure, and can thus be seen as a combinatorial representation of a dynamical system. Here we explore in some detail the relation between visibility graphs and symbolic dynamics. To do that, we consider the degree sequence of horizontal visibility graphs generated by the one-parameter logistic map, for a range of values of the parameter for which the map shows chaotic behaviour. Numerically, we observe that in the chaotic region the block entropies of these sequences systematically converge to the Lyapunov exponent of the system. Via Pesin identity, this in turn suggests that these block entropies are converging to the Kolmogorov- Sinai entropy of the map, which ultimately suggests that the algorithm is implicitly and adaptively constructing phase space partitions which might have the generating property. To give analytical insight, we explore the relation k(x), x \in[0,1] that, for a given datum with value x, assigns in graph space a node with degree k. In the case of the out-degree sequence, such relation is indeed a piece-wise constant function. By making use of explicit methods and tools from symbolic dynamics we are able to analytically show that the algorithm indeed performs an effective partition of the phase space and that such partition is naturally expressed as a countable union of subintervals, where the endpoints of each subinterval are related to the fixed point structure of the iterates of the map and the subinterval enumeration is associated with particular ordering structures that we called motifs.
]]></description>
<dc:subject>nonlinear-dynamics feature-construction rather-interesting representation discretization graph-theory time-series to-understand to-write-about consider:a-little-library numerical-methods chaos</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:f7b7ad957779/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nonlinear-dynamics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discretization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:time-series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:a-little-library"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:numerical-methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:chaos"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1605.02713">
    <title>[1605.02713] The Avalanche Polynomial of a Graph</title>
    <dc:date>2022-01-23T12:50:00+00:00</dc:date>
    <link>https://arxiv.org/abs/1605.02713</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[The (univariate) avalanche polynomial of a graph, introduced by Cori, Dartois and Rossin in 2006, captures the distribution of the length of (principal) avalanches in the abelian sandpile model. This polynomial has been used to show that the avalanche distribution in the sandpile model on a multiple wheel graph does not follow the expected power law function. In this article, we introduce the (multivariate) avalanche polynomial that enumerates the toppling sequences of all principal avalanches. This polynomial generalizes the univariate avalanche polynomial and encodes more information. In particular, the avalanche polynomial of a tree uniquely identifies the underlying tree. In this paper, the avalanche polynomial is characterized for trees, cycles, wheels, and complete graphs.
]]></description>
<dc:subject>self-organization sandpiles feature-construction graph-theory rather-interesting to-write-about to-visualize consider:extreme-hunting consider:prediction</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:4b7104eff49a/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:self-organization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:sandpiles"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-visualize"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:extreme-hunting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:prediction"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2111.02992">
    <title>[2111.02992] The Shortest Even Cycle Problem is Tractable</title>
    <dc:date>2022-01-22T12:57:29+00:00</dc:date>
    <link>https://arxiv.org/abs/2111.02992</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Given a directed graph, we show how to efficiently find a shortest (directed, simple) cycle on an even number of vertices. As far as we know, no polynomial-time algorithm was previously known for this problem. In fact, finding any even cycle in a directed graph in polynomial time was open for more than two decades until Robertson, Seymour, and Thomas (Ann. of Math. (2) 1999) and, independently, McCuaig (Electron. J. Combin. 2004; announced jointly at STOC 1997) gave an efficiently testable structural characterisation of even-cycle-free directed graphs. 
Methodologically, our algorithm relies on algebraic fingerprinting and randomized polynomial identity testing over a finite field, and uses a generating polynomial implicit in Vazirani and Yannakakis ( Discrete Appl. Math. 1989) that enumerates weighted cycle covers as a difference of a permanent and a determinant polynomial. The need to work with the permanent is where our main technical contribution occurs. We design a family of finite commutative rings of characteristic 4 that simultaneously (i) give a nondegenerate representation for the generating polynomial identity via the permanent and the determinant, (ii) support efficient permanent computations, and (iii) enable emulation of finite-field arithmetic in characteristic 2. Here our work is foreshadowed by that of Björklund and Husfeldt (SIAM J. Comput. 2019), who used a considerably less efficient ring design to obtain a polynomial-time algorithm for the shortest two disjoint paths problem. 
Building on work of Gilbert and Tarjan (Numer. Math. 1978) as well as Alon and Yuster (J. ACM 2013), we also show how ideas from the nested dissection technique for solving linear equation systems leads to faster algorithm designs when we have control on the separator structure of the input graph; for example, this happens when the input has bounded genus.
]]></description>
<dc:subject>computational-complexity algorithms graph-theory rather-interesting nudge-targets consider:representation consider:rediscovery</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:c79ed6a6c051/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:nudge-targets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:rediscovery"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2011.02735">
    <title>[2011.02735] Monadic second-order logic and the domino problem on self-similar graphs</title>
    <dc:date>2021-10-22T10:35:06+00:00</dc:date>
    <link>https://arxiv.org/abs/2011.02735</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We consider the domino problem on Schreier graphs of self-similar groups, and more generally their monadic second-order logic. On the one hand, we prove that if the group is bounded then the graph's monadic second-order logic is decidable. This covers, for example, the Sierpiński gasket graphs and the Schreier graphs of the Basilica group. On the other hand, we already prove undecidability of the domino problem for a class of self-similar groups, answering a question by Barbieri and Sablik, and some examples including one of linear growth.
]]></description>
<dc:subject>group-theory graph-theory rather-interesting information-theory algorithms to-understand computational-complexity unanswerable-questions formal-languages</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:589ef3cd7bc6/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:group-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:information-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:unanswerable-questions"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:formal-languages"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1612.07276">
    <title>[1612.07276] Splitting $B_2$-VPG graphs into outer-string and co-comparability graphs</title>
    <dc:date>2021-10-06T11:29:16+00:00</dc:date>
    <link>https://arxiv.org/abs/1612.07276</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[In this paper, we show that any B2-VPG graph (i.e., an intersection graph of orthogonal curves with at most 2 bends) can be decomposed into O(logn) outerstring graphs or O(log3n) permutation graphs. This leads to better approximation algorithms for hereditary graph problems, such as independent set, clique and clique cover, on B2-VPG graphs.]]></description>
<dc:subject>graph-theory combinatorics geometric-graphs intersection-graphs rather-interesting consider:all-those-constraints consider:simulation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:2c38eb6cd83f/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:geometric-graphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:intersection-graphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:all-those-constraints"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:simulation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1803.03468">
    <title>[1803.03468] On contact graphs of paths on a grid</title>
    <dc:date>2021-10-03T20:09:22+00:00</dc:date>
    <link>https://arxiv.org/abs/1803.03468</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[In this paper we consider Contact graphs of Paths on a Grid (CPG graphs), i.e. graphs for which there exists a family of interiorly disjoint paths on a grid in one-to-one correspondence with their vertex set such that two vertices are adjacent if and only if the corresponding paths touch at a grid-point. Our class generalizes the well studied class of VCPG graphs (see [1]). We examine CPG graphs from a structural point of view which leads to constant upper bounds on the clique number and the chromatic number. Moreover, we investigate the recognition and 3-colorability problems for B0-CPG, a subclass of CPG. We further show that CPG graphs are not necessarily planar and not all planar graphs are CPG.
]]></description>
<dc:subject>graph-theory geometric-graphs enumeration combinatorics rather-interesting to-understand to-simulate</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:17d0c07ed948/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:geometric-graphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:enumeration"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1903.01805">
    <title>[1903.01805] CPG graphs: Some structural and hardness results</title>
    <dc:date>2021-10-03T20:07:02+00:00</dc:date>
    <link>https://arxiv.org/abs/1903.01805</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[In this paper we continue the systematic study of Contact graphs of Paths on a Grid (CPG graphs) initiated in [Deniz et al., 2018]. A CPG graph is a graph for which there exists a collection of pairwise interiorly disjoint paths on a grid in one-to-one correspondence with its vertex set such that two vertices are adjacent if and only if the corresponding paths touch at a grid-point. If every such path has at most k bends for some k≥0, the graph is said to be Bk-CPG. 
We first show that, for any k≥0, the class of Bk-CPG graphs is strictly contained in the class of Bk+1-CPG graphs even within the class of planar graphs, thus implying that there exists no k≥0 such that every planar CPG graph is Bk-CPG. The main result of the paper is that recognizing CPG graphs and Bk-CPG graphs with k≥1 is 𝖭𝖯-complete. Moreover, we show that the same remains true even within the class of planar graphs in the case k≥3. We then consider several graph problems restricted to CPG graphs and show, in particular, that Independent Set and Clique Cover remain 𝖭𝖯-hard for B0-CPG graphs. Finally, we consider the related classes Bk-EPG of edge-intersection graphs of paths with at most k bends on a grid. Although it is possible to optimally color a B0-EPG graph in polynomial time, as this class coincides with that of interval graphs, we show that, in contrast, 3-Colorability is 𝖭𝖯-complete for B1-EPG graphs.]]></description>
<dc:subject>graph-theory geometric-graphs kinda-sorta enumeration looking-to-see to-write-about consider:enumeration consider:games</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:baf2e279d4e9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:geometric-graphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:kinda-sorta"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:enumeration"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:enumeration"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:games"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1901.07842">
    <title>[1901.07842] The Firebreak Problem</title>
    <dc:date>2021-10-03T20:02:21+00:00</dc:date>
    <link>https://arxiv.org/abs/1901.07842</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Suppose we have a network that is represented by a graph G. Potentially a fire (or other type of contagion) might erupt at some vertex of G. We are able to respond to this outbreak by establishing a firebreak at k other vertices of G, so that the fire cannot pass through these fortified vertices. The question that now arises is which k vertices will result in the greatest number of vertices being saved from the fire, assuming that the fire will spread to every vertex that is not fully behind the k vertices of the firebreak. This is the essence of the {\sc Firebreak} decision problem, which is the focus of this paper. We establish that the problem is intractable on the class of split graphs as well as on the class of bipartite graphs, but can be solved in linear time when restricted to graphs having constant-bounded treewidth, or in polynomial time when restricted to intersection graphs. We also consider some closely related problems.
]]></description>
<dc:subject>graph-theory feature-construction computational-complexity algorithms rather-interesting to-write-about to-visualize consider:random-sampling</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:65803e19bf3a/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-visualize"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:random-sampling"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1512.02381">
    <title>[1512.02381] Box representations of embedded graphs</title>
    <dc:date>2021-10-02T00:18:26+00:00</dc:date>
    <link>https://arxiv.org/abs/1512.02381</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[A d-box is the cartesian product of d intervals of ℝ and a d-box representation of a graph G is a representation of G as the intersection graph of a set of d-boxes in ℝd. It was proved by Thomassen in 1986 that every planar graph has a 3-box representation. In this paper we prove that every graph embedded in a fixed orientable surface, without short non-contractible cycles, has a 5-box representation. This directly implies that there is a function f, such that in every graph of genus g, a set of at most f(g) vertices can be removed so that the resulting graph has a 5-box representation. We show that such a function f can be made linear in g. Finally, we prove that for any proper minor-closed class , there is a constant c() such that every graph of  without cycles of length less than c() has a 3-box representation, which is best possible.]]></description>
<dc:subject>graph-theory representation rather-interesting to-write-about consider:uniform-sampling consider:looking-to-see consider:visualization</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:fe3bae00fd01/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:uniform-sampling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:visualization"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1603.08974">
    <title>[1603.08974] Refining the Hierarchies of Classes of Geometric Intersection Graphs</title>
    <dc:date>2021-10-02T00:11:34+00:00</dc:date>
    <link>https://arxiv.org/abs/1603.08974</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We analyse properties of geometric intersection graphs to show the strict containment between some natural classes of geometric intersection graphs. In particular, we show the following properties: 
- A graph G is outerplanar if and only if the 1-subdivision of G is outer-segment. 
- For each integer k≥1, the class of intersection graphs of segments with k different lengths is a strict subclass of the class of intersection graphs of segments with k+1 different lengths. 
- For each integer k≥1, the class of intersection graphs of disks with k different sizes is a strict subclass of the class of intersection graphs of disks with k+1 different sizes. 
- The class of outer-segment graphs is a strict subclass of the class of outer-string graphs.
]]></description>
<dc:subject>graph-theory combinatorics classification intersection-graphs to-understand feature-selection</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:4e98fc660c69/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:classification"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:intersection-graphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-selection"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2010.05518">
    <title>[2010.05518] Fibonacci-run graphs I: basic properties</title>
    <dc:date>2021-07-12T09:45:59+00:00</dc:date>
    <link>https://arxiv.org/abs/2010.05518</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Among the classical models for interconnection networks are hypercubes and Fibonacci cubes. Fibonacci cubes are induced subgraphs of hypercubes obtained by restricting the vertex set to those binary strings which do not contain consecutive 1s, counted by Fibonacci numbers. Another set of binary strings which are counted by Fibonacci numbers are those with a restriction on the runlengths. Induced subgraphs of the hypercube on the latter strings as vertices define Fibonacci-run graphs. They have the same number of vertices as Fibonacci cubes, but fewer edges and different connectivity properties. 
We obtain properties of Fibonacci-run graphs including the number of edges, the analogue of the fundamental recursion, the average degree of a vertex, Hamiltonicity, special degree sequences, and the number of hypercubes they contain. A detailed study of the degree sequences of Fibonacci-run graphs is interesting in its own right and is reported in a companion paper.
]]></description>
<dc:subject>combinatorics graph-theory rewriting-systems enumeration rather-interesting representation hypercubes fitness-landscapes</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:fa51fc459181/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rewriting-systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:enumeration"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:hypercubes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:fitness-landscapes"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2101.12560">
    <title>[2101.12560] The iterated local transitivity model for hypergraphs</title>
    <dc:date>2021-07-11T11:52:05+00:00</dc:date>
    <link>https://arxiv.org/abs/2101.12560</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Complex networks are pervasive in the real world, capturing dyadic interactions between pairs of vertices, and a large corpus has emerged on their mining and modeling. However, many phenomena are comprised of polyadic interactions between more than two vertices. Such complex hypergraphs range from emails among groups of individuals, scholarly collaboration, or joint interactions of proteins in living cells. 
A key generative principle within social and other complex networks is transitivity, where friends of friends are more likely friends. The previously proposed Iterated Local Transitivity (ILT) model incorporated transitivity as an evolutionary mechanism. The ILT model provably satisfies many observed properties of social networks, such as densification, low average distances, and high clustering coefficients. 
We propose a new, generative model for complex hypergraphs based on transitivity, called the Iterated Local Transitivity Hypergraph (or ILTH) model. In ILTH, we iteratively apply the principle of transitivity to form new hypergraphs. The resulting model generates hypergraphs simulating properties observed in real-world complex hypergraphs, such as densification and low average distances. We consider properties unique to hypergraphs not captured by their 2-section. We show that certain motifs, which are specified subhypergraphs of small order, have faster growth rates in ILTH hypergraphs than in random hypergraphs with the same order and expected average degree. We show that the graphs admitting a homomorphism into the 2-section of the initial hypergraph appear as induced subgraphs in the 2-section of ILTH hypergraphs. We consider new and existing hypergraph clustering coefficients, and show that these coefficients have larger values in ILTH hypergraphs than in comparable random hypergraphs.
]]></description>
<dc:subject>hypergraphs feature-extraction graph-theory rather-interesting enumeration classification formalization to-understand to-write-about to-visualize</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:4240703128bd/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:hypergraphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-extraction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:enumeration"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:classification"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:formalization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-visualize"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2105.06150">
    <title>[2105.06150] An Algorithm for Limited Visibility Graph Searching</title>
    <dc:date>2021-06-05T11:34:21+00:00</dc:date>
    <link>https://arxiv.org/abs/2105.06150</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We study a graph search problem in which a team of searchers attempts to find a mobile target located in a graph. Assuming that (a) the visibility field of the searchers is limited, (b) the searchers have unit speed and (c) the target has infinite speed, we formulate the Limited Visibility Graph Search (LVGS) problem and present the LVGS algorithm, which produces a search schedule guaranteed to find the target in the minimum possible number of steps. Our LVGS algorithm is a conversion of Guibas and Lavalle's polygonal region search algorithm.
]]></description>
<dc:subject>graph-theory feature-construction rather-interesting game-theory computational-geometry optimization planning to-write-about to-simulate</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:a46a40e22faa/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:game-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-geometry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:planning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1902.10752">
    <title>[1902.10752] Formal structure of periodic system of elements</title>
    <dc:date>2021-05-28T17:36:01+00:00</dc:date>
    <link>https://arxiv.org/abs/1902.10752</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[For more than 150 years the structure of the periodic system of the chemical elements has intensively motivated research in different areas of chemistry and physics. However, there is still no unified picture of what a periodic system is. Herein, based on the relations of order and similarity, we report a formal mathematical structure for the periodic system, which corresponds to an ordered hypergraph. It is shown that the current periodic system of chemical elements is an instance of the general structure. The definition is used to devise a tailored periodic system of polarizability of single covalent bonds, where order relationships are quantified within subsets of similar bonds and among these classes. The generalised periodic system allows envisioning periodic systems in other disciplines of science and humanities.
]]></description>
<dc:subject>chemistry periodic-table discrete-mathematics rather-interesting looking-to-see formalization graph-theory hypergraphs order-relationships</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:d75298a8d136/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:chemistry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:periodic-table"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:discrete-mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:formalization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:hypergraphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:order-relationships"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1802.06478">
    <title>[1802.06478] An Efficient Local Search for the Minimum Independent Dominating Set Problem</title>
    <dc:date>2021-05-26T10:27:40+00:00</dc:date>
    <link>https://arxiv.org/abs/1802.06478</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[In the present paper, we propose an efficient local search for the minimum independent dominating set problem. We consider a local search that uses k-swap as the neighborhood operation. Given a feasible solution S, it is the operation of obtaining another feasible solution by dropping exactly k vertices from S and then by adding any number of vertices to it. We show that, when k=2, (resp., k=3 and a given solution is minimal with respect to 2-swap), we can find an improved solution in the neighborhood or conclude that no such solution exists in O(nΔ) (resp., O(nΔ3)) time, where n denotes the number of vertices and Δ denotes the maximum degree. We develop a metaheuristic algorithm that repeats the proposed local search and the plateau search iteratively, where the plateau search examines solutions of the same size as the current solution that are obtainable by exchanging a solution vertex and a non-solution vertex. The algorithm is so effective that, among 80 DIMACS graphs, it updates the best-known solution size for five graphs and performs as well as existing methods for the remaining graphs.
]]></description>
<dc:subject>graph-theory algorithms computational-complexity to-write-about consider:visualization consider:genetic-programming</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:73463940e0aa/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:visualization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:genetic-programming"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2102.05738">
    <title>[2102.05738] Refinement of polygonal grids using Convolutional Neural Networks with applications to polygonal Discontinous Galerkin and Virtual Element methods</title>
    <dc:date>2021-05-19T10:55:00+00:00</dc:date>
    <link>https://arxiv.org/abs/2102.05738</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We propose new strategies to handle polygonal grids refinement based on Convolutional Neural Networks (CNNs). We show that CNNs can be successfully employed to identify correctly the "shape" of a polygonal element so as to design suitable refinement criteria to be possibly employed within adaptive refinement strategies. We propose two refinement strategies that exploit the use of CNNs to classify elements' shape, at a low computational cost. We test the proposed idea considering two families of finite element methods that support arbitrarily shaped polygonal elements, namely Polygonal Discontinuous Galerkin (PolyDG) methods and Virtual Element Methods (VEMs). We demonstrate that the proposed algorithms can greatly improve the performance of the discretization schemes both in terms of accuracy and quality of the underlying grids. Moreover, since the training phase is performed off-line and is problem independent the overall computational costs are kept low.
]]></description>
<dc:subject>neural-networks lattices graph-theory performance-measure plane-geometry to-understand consider:performance-measures</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:4d9cc5f1474e/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:neural-networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:lattices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:performance-measure"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:plane-geometry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:performance-measures"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://github.com/simongray/clojure-graph-resources#datalog">
    <title>simongray/clojure-graph-resources: A curated list of Clojure resources for dealing with graph-like data.</title>
    <dc:date>2021-05-18T22:11:54+00:00</dc:date>
    <link>https://github.com/simongray/clojure-graph-resources#datalog</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[This is a curated list of mostly mature and/or actively developed Clojure resources relevant for dealing with graph-like data. It's currently being expanded as I explore this area more thoroughly. Suggestions are welcome in the form of pull requests or Github issues. I try to steer around abandonware, though.

]]></description>
<dc:subject>clojure libraries graph-theory software-development-is-not-programming to-understand</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:b3cf798e7017/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:clojure"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:libraries"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:software-development-is-not-programming"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2002.04025">
    <title>[2002.04025] Can Graph Neural Networks Count Substructures?</title>
    <dc:date>2021-05-18T10:32:29+00:00</dc:date>
    <link>https://arxiv.org/abs/2002.04025</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[The ability to detect and count certain substructures in graphs is important for solving many tasks on graph-structured data, especially in the contexts of computational chemistry and biology as well as social network analysis. Inspired by this, we propose to study the expressive power of graph neural networks (GNNs) via their ability to count attributed graph substructures, extending recent works that examine their power in graph isomorphism testing and function approximation. We distinguish between two types of substructure counting: induced-subgraph-count and subgraph-count, and establish both positive and negative answers for popular GNN architectures. Specifically, we prove that Message Passing Neural Networks (MPNNs), 2-Weisfeiler-Lehman (2-WL) and 2-Invariant Graph Networks (2-IGNs) cannot perform induced-subgraph-count of substructures consisting of 3 or more nodes, while they can perform subgraph-count of star-shaped substructures. As an intermediary step, we prove that 2-WL and 2-IGNs are equivalent in distinguishing non-isomorphic graphs, partly answering an open problem raised in Maron et al. (2019). We also prove positive results for k-WL and k-IGNs as well as negative results for k-WL with a finite number of iterations. We then conduct experiments that support the theoretical results for MPNNs and 2-IGNs. Moreover, motivated by substructure counting and inspired by Murphy et al. (2019), we propose the Local Relational Pooling model and demonstrate that it is not only effective for substructure counting but also able to achieve competitive performance on molecular prediction tasks.
]]></description>
<dc:subject>neural-networks representation algorithms graph-theory to-write-about to-simulate consider:genetic-programming consider:performance-measures</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:695e44aefbc2/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:neural-networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:genetic-programming"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:performance-measures"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2104.14863">
    <title>[2104.14863] Reconstruction of hypergraphs from line graphs and degree sequences</title>
    <dc:date>2021-05-07T16:20:35+00:00</dc:date>
    <link>https://arxiv.org/abs/2104.14863</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[In this paper we consider the problem to reconstruct a k-uniform hypergraph from its line graph. In general this problem is hard. We solve this problem when the number of hyperedges containing any pair of vertices is bounded. Given an integer sequence, constructing a k-uniform hypergraph with that as its degree sequence is NP-complete. Here we show that for constant integer sequences the question can be answered in polynomial time using Baranyai's theorem.
]]></description>
<dc:subject>hypergraphs inference symmetry graph-theory rather-interesting inference? to-understand to-simulate</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:9e7017d2e481/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:hypergraphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:inference"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:symmetry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:inference?"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://www.youtube.com/channel/UC6j-G6oPmkqCgOx6UQOUhSQ">
    <title>GReTA Seminar - YouTube</title>
    <dc:date>2021-01-22T17:14:30+00:00</dc:date>
    <link>https://www.youtube.com/channel/UC6j-G6oPmkqCgOx6UQOUhSQ</link>
    <dc:creator>Vaguery</dc:creator><dc:subject>graph-theory rewriting-systems rather-interesting seminars academic-culture to-watch</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:deafddc8a02a/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rewriting-systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:seminars"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:academic-culture"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-watch"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://imaginary.org/snapshot/limits-of-graph-sequences">
    <title>Limits of graph sequences | IMAGINARY</title>
    <dc:date>2020-11-13T23:36:42+00:00</dc:date>
    <link>https://imaginary.org/snapshot/limits-of-graph-sequences</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Graphs are simple mathematical structures used to model a wide variety of real-life objects. With the rise of computers, the size of the graphs used for these models has grown enormously. The need to efficiently represent and study properties of extremely large graphs led to the development of the theory of graph limits.

]]></description>
<dc:subject>graph-theory graphons rather-interesting to-write-about consider:random-ones consider:limits</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:567f8cf881a3/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graphons"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:random-ones"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:limits"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1912.05251">
    <title>[1912.05251] Colouring bottomless rectangles and arborescences</title>
    <dc:date>2020-10-07T15:45:41+00:00</dc:date>
    <link>https://arxiv.org/abs/1912.05251</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We study problems related to colouring bottomless rectangles. One of our main results shows that for any positive integers m,k, there is no semi-online algorithm that can k-colour bottomless rectangles with disjoint boundaries in increasing order of their top sides, so that any m-fold covered point is covered by at least two colours. This is, surprisingly, a corollary of a stronger result for arborescence colourings. Any semi-online colouring algorithm that colours an arborescence in leaf-to-root order with a bounded number of colours produces arbitrarily long monochromatic paths. This is complemented by optimal upper bounds given by simple online colouring algorithms from other directions. 
Our other main results study configurations of bottomless rectangles in an attempt to improve the \textit{polychromatic k-colouring number}, m∗k. We show that for many families of bottomless rectangles, such as unit-width bottomless rectangles, m∗k is linear in k. We also present an improved lower bound for general families: m∗k≥2k−1.
]]></description>
<dc:subject>hypergraphs graph-theory algorithms impossibility proof rather-interesting to-write-about to-simulate consider:guessing consider:visualization combinatorics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:627f1dbc878b/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:hypergraphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:impossibility"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:proof"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:guessing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:visualization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://www.quantamagazine.org/a-new-algorithm-for-graph-crossings-hiding-in-plain-sight-20200915/">
    <title>A New Algorithm for Graph Crossings, Hiding in Plain Sight | Quanta Magazine</title>
    <dc:date>2020-10-03T12:14:28+00:00</dc:date>
    <link>https://www.quantamagazine.org/a-new-algorithm-for-graph-crossings-hiding-in-plain-sight-20200915/</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[What they belatedly recognized in October was that a flip that brings you closer to being able to add a new edge also brings the graph closer to resembling one of the good drawings they’d already identified. By showing that a series of flips inevitably moves a graph toward a favorable drawing, the new algorithm puts a backstop on the number of flips you could possibly need to perform before finding a way to insert an edge (provided the insertion is possible at all).

]]></description>
<dc:subject>see-prior-bookmark graph-theory computational-complexity graph-layout rather-interesting algorithms to-write-about to-simulate</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:38d10dff7d32/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:see-prior-bookmark"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-layout"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1911.03449">
    <title>[1911.03449] Fully-dynamic Planarity Testing in Polylogarithmic Time</title>
    <dc:date>2020-10-03T12:12:51+00:00</dc:date>
    <link>https://arxiv.org/abs/1911.03449</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Given a dynamic graph subject to insertions and deletions of edges, a natural question is whether the graph presently admits a planar embedding. We give a deterministic fully-dynamic algorithm for general graphs, running in amortized O(log3n) time per edge insertion or deletion, that maintains a bit indicating whether or not the graph is presently planar. This is an exponential improvement over the previous best algorithm [Eppstein, Galil, Italiano, Spencer, 1996] which spends amortized O(n‾√) time per update.
]]></description>
<dc:subject>algorithms computational-complexity computational-geometry graph-theory rather-interesting to-understand to-write-about consider:rediscovery consider:representation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:7a3792b8651e/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-geometry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:rediscovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:representation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1605.08640">
    <title>[1605.08640] Arithmetical Semirings</title>
    <dc:date>2020-09-19T12:31:18+00:00</dc:date>
    <link>https://arxiv.org/abs/1605.08640</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We study the number of connected graphs with n vertices that cannot be written as the cartesian product of two graphs with fewer vertices. We give an upper bound which implies that for large n almost all graphs are both connected and cartesian prime. For graphs with an even number of vertices, a full asymptotic expansion is obtained. Our method, inspired by Knopfmacher's theory of arithmetical semigroups, is based on reduction to Wright's asymptotic expansion for the number of connected graphs with n vertices.
]]></description>
<dc:subject>graph-theory combinatorics counting number-theory group-theory to-understand to-reread consider:visualization to-write-about consider:feature-discovery</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:fdd0dcff9ac0/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:counting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:number-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:group-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-reread"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:visualization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:feature-discovery"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1704.07067">
    <title>[1704.07067] Rerouting flows when links fail</title>
    <dc:date>2020-07-22T14:37:31+00:00</dc:date>
    <link>https://arxiv.org/abs/1704.07067</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We introduce and investigate reroutable flows, a robust version of network flows in which link failures can be mitigated by rerouting the affected flow. Given a capacitated network, a path flow is reroutable if after failure of an arbitrary arc, we can reroute the interrupted flow from the tail of that arc to the sink, without modifying the flow that is not affected by the failure. Similar types of restoration, which are often termed "local", were previously investigated in the context of network design, such as min-cost capacity planning. In this paper, our interest is in computing maximum flows under this robustness assumption. An important new feature of our model, distinguishing it from existing max robust flow models, is that no flow can get lost in the network. 
We also study a tightening of reroutable flows, called strictly reroutable flows, making more restrictive assumptions on the capacities available for rerouting. For both variants, we devise a reroutable-flow equivalent of an s-t-cut and show that the corresponding max flow/min cut gap is bounded by 2. It turns out that a strictly reroutable flow of maximum value can be found using a compact LP formulation, whereas the problem of finding a maximum reroutable flow is NP-hard, even when all capacities are in {1, 2}. However, the tightening can be used to get a 2-approximation for reroutable flows. This ratio is tight in general networks, but we show that in the case of unit capacities, every reroutable flow can be transformed into a strictly reroutable flow of same value. While it is NP-hard to compute a maximal integral flow even for unit capacities, we devise a surprisingly simple combinatorial algorithm that finds a half-integral strictly reroutable flow of value 1, or certifies that no such solutions exits. Finally, we also give a hardness result for the case of multiple arc failures.
]]></description>
<dc:subject>graph-theory algorithms network-theory operations-research optimization robustness performance-measure rather-interesting to-write-about to-simulate</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:51a64f47738d/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:network-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:operations-research"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:robustness"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:performance-measure"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1607.07426">
    <title>[1607.07426] Symmetric Graphs have symmetric Matchings</title>
    <dc:date>2020-07-21T17:29:18+00:00</dc:date>
    <link>https://arxiv.org/abs/1607.07426</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Assume that there is a free group action of automorphisms on a bipartite graph. If there is a perfect matching on the factor graph, then obviously there is a perfect matching on the graph. Surprisingly, the reversed is also true for amenable groups: if there is a perfect matching on the graph, there is also a perfect matching on the factor graph, i. e. a group invariant ("symmetric") perfect matching on the graph.
]]></description>
<dc:subject>graph-theory rather-interesting feature-construction open-questions to-write-about consider:background consider:visualization</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:2d3b1adfa7a7/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:open-questions"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:background"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:visualization"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1703.10293">
    <title>[1703.10293] Preserving Distances in Very Faulty Graphs</title>
    <dc:date>2020-07-15T13:46:05+00:00</dc:date>
    <link>https://arxiv.org/abs/1703.10293</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Preservers and additive spanners are sparse (hence cheap to store) subgraphs that preserve the distances between given pairs of nodes exactly or with some small additive error, respectively. Since real-world networks are prone to failures, it makes sense to study fault-tolerant versions of the above structures. This turns out to be a surprisingly difficult task. For every small but arbitrary set of edge or vertex failures, the preservers and spanners need to contain {\em replacement paths} around the faulted set. In this paper we make substantial progress on fault tolerant preservers and additive spanners: 
(1) We present the first truly sub-quadratic size single-pair preservers in unweighted (possibly directed) graphs for \emph{any} fixed number f of faults. Our result indeed generalizes to the single-source case, and can be used to build new fault-tolerant additive spanners (for all pairs). 
(2) The size of the above single-pair preservers is O(n2−g(f)) for some positive function g, and grows to O(n2) for increasing f. We show that this is necessary even in undirected unweighted graphs, and even if you allow for a small additive error: If you aim at size O(n2−ϵ) for ϵ>0, then the additive error has to be $\Omega(\eps f)$. This surprisingly matches known upper bounds in the literature. 
(3) For weighted graphs, we provide matching upper and lower bounds for the single pair case. Namely, the size of the preserver is Θ(n2) for f≥2 in both directed and undirected graphs, while for f=1 the size is Θ(n) in undirected graphs. For directed graphs, we have a superlinear upper bound and a matching lower bound. 
Most of our lower bounds extend to the distance oracle setting, where rather than a subgraph we ask for any compact data structure.
]]></description>
<dc:subject>network-theory robustness rather-interesting algorithms computational-complexity graph-theory to-write-about to-simulate consider:looking-to-see consider:feature-discovery</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:2475359bbfb8/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:network-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:robustness"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:feature-discovery"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1909.03152">
    <title>[1909.03152] Graph Spanners: A Tutorial Review</title>
    <dc:date>2020-05-26T11:36:10+00:00</dc:date>
    <link>https://arxiv.org/abs/1909.03152</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[This tutorial review provides a guiding reference to researchers who want to have an overview of the large body of literature about graph spanners. It reviews the current literature covering various research streams about graph spanners, such as different formulations, sparsity and lightness results, computational complexity, dynamic algorithms, and applications. As an additional contribution, we offer a list of open problems on graph spanners.
]]></description>
<dc:subject>tutorial graph-theory approximation heuristics rather-interesting to-write-about to-simulate consider:random-guesses consider:relaxation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:9e7af9693e7f/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:tutorial"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:heuristics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:random-guesses"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:relaxation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2002.06421">
    <title>[2002.06421] Kruskal-based approximation algorithm for the multi-level Steiner tree problem</title>
    <dc:date>2020-05-26T11:32:05+00:00</dc:date>
    <link>https://arxiv.org/abs/2002.06421</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We study the multi-level Steiner tree problem: a generalization of the Steiner tree problem in graphs where terminals T require varying priority, level, or quality of service. In this problem, we seek to find a minimum cost tree containing edges of varying rates such that any two terminals u, v with priorities P(u), P(v) are connected using edges of rate min{P(u),P(v)} or better. The case where edge costs are proportional to their rate is approximable to within a constant factor of the optimal solution. For the more general case of non-proportional costs, this problem is hard to approximate with ratio cloglogn, where n is the number of vertices in the graph. A simple greedy algorithm by Charikar et al., however, provides a min{2(ln|T|+1),ℓρ}-approximation in this setting, where ρ is an approximation ratio for a heuristic solver for the Steiner tree problem and ℓ is the number of priorities or levels (Byrka et al. give a Steiner tree algorithm with ρ≈1.39, for example). 
In this paper, we describe a natural generalization to the multi-level case of the classical (single-level) Steiner tree approximation algorithm based on Kruskal's minimum spanning tree algorithm. We prove that this algorithm achieves an approximation ratio at least as good as Charikar et al., and experimentally performs better with respect to the optimum solution. We develop an integer linear programming formulation to compute an exact solution for the multi-level Steiner tree problem with non-proportional edge costs and use it to evaluate the performance of our algorithm on both random graphs and multi-level instances derived from SteinLib.
]]></description>
<dc:subject>optimization computational-geometry graph-theory geometric-graphs planning rather-interesting to-simulate to-write-about</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:0edb21cbda36/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-geometry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:geometric-graphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:planning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1506.04380">
    <title>[1506.04380] Structure of Graphs with Locally Restricted Crossings</title>
    <dc:date>2020-05-24T10:47:49+00:00</dc:date>
    <link>https://arxiv.org/abs/1506.04380</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We consider relations between the size, treewidth, and local crossing number (maximum number of crossings per edge) of graphs embedded on topological surfaces. We show that an n-vertex graph embedded on a surface of genus g with at most k crossings per edge has treewidth O((g+1)(k+1)n‾‾‾‾‾‾‾‾‾‾‾‾‾‾√) and layered treewidth O((g+1)k), and that these bounds are tight up to a constant factor. As a special case, the k-planar graphs with n vertices have treewidth O((k+1)n‾‾‾‾‾‾‾‾√) and layered treewidth O(k+1), which are tight bounds that improve a previously known O((k+1)3/4n1/2) treewidth bound. Analogous results are proved for map graphs defined with respect to any surface. Finally, we show that for g<m, every m-edge graph can be embedded on a surface of genus~g with O((m/(g+1))log2g) crossings per edge, which is tight to a polylogarithmic factor.
]]></description>
<dc:subject>graph-theory graph-layout graph-embedding rather-interesting combinatorics to-write-about to-simulate consider:algorithms consider:relaxations</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:131f588a3872/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-layout"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-embedding"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:relaxations"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2004.13491">
    <title>[2004.13491] As Time Goes By: Reflections on Treewidth for Temporal Graphs</title>
    <dc:date>2020-05-23T11:50:19+00:00</dc:date>
    <link>https://arxiv.org/abs/2004.13491</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Treewidth is arguably the most important structural graph parameter leading to algorithmically beneficial graph decompositions. Triggered by a strongly growing interest in temporal networks (graphs where edge sets change over time), we discuss fresh algorithmic views on temporal tree decompositions and temporal treewidth. We review and explain some of the recent work together with some encountered pitfalls, and we point out challenges for future research.
]]></description>
<dc:subject>data-structures graph-theory dynamical-systems algorithms to-write-about to-simulate consider:looking-to-see consider:autocorrelation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:acf02c840c2a/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:data-structures"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:dynamical-systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:autocorrelation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1904.08746">
    <title>[1904.08746] Advancing Through Terrains</title>
    <dc:date>2020-05-23T11:38:20+00:00</dc:date>
    <link>https://arxiv.org/abs/1904.08746</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We study terrain visibility graphs, a well-known graph class closely related to polygon visibility graphs in computational geometry, for which a precise graph-theoretical characterization is still unknown. Over the last decade, terrain visibility graphs attracted attention in the context of time series analysis with various practical applications in areas such as physics, geography and medical sciences. We make progress in understanding terrain visibility graphs by providing several graph-theoretic results. For example, we show that they cannot contain antiholes of size larger than five. Moreover, we obtain two algorithmic results. We devise a fast output-sensitive shortest path algorithm on arbitrary induced subgraphs of terrain visibility graphs and a polynomial-time algorithm for \textsc{Dominating Set} on special terrain visibility graphs (called funnel visibility graphs).
]]></description>
<dc:subject>computational-geometry graph-theory geometric-graphs rather-interesting visibility-problems classification to-write-about to-simulate consider:constraint-satisfaction</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:12d259dcc0ff/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-geometry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:geometric-graphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:visibility-problems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:classification"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:constraint-satisfaction"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1705.01595">
    <title>[1705.01595] Homomorphisms Are a Good Basis for Counting Small Subgraphs</title>
    <dc:date>2020-05-22T21:22:08+00:00</dc:date>
    <link>https://arxiv.org/abs/1705.01595</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We introduce graph motif parameters, a class of graph parameters that depend only on the frequencies of constant-size induced subgraphs. Classical works by Lovász show that many interesting quantities have this form, including, for fixed graphs H, the number of H-copies (induced or not) in an input graph G, and the number of homomorphisms from H to G. 
Using the framework of graph motif parameters, we obtain faster algorithms for counting subgraph copies of fixed graphs H in host graphs G: For graphs H on k edges, we show how to count subgraph copies of H in time kO(k)⋅n0.174k+o(k) by a surprisingly simple algorithm. This improves upon previously known running times, such as O(n0.91k+c) time for k-edge matchings or O(n0.46k+c) time for k-cycles. 
Furthermore, we prove a general complexity dichotomy for evaluating graph motif parameters: Given a class  of such parameters, we consider the problem of evaluating f∈ on input graphs G, parameterized by the number of induced subgraphs that f depends upon. For every recursively enumerable class , we prove the above problem to be either FPT or #W[1]-hard, with an explicit dichotomy criterion. This allows us to recover known dichotomies for counting subgraphs, induced subgraphs, and homomorphisms in a uniform and simplified way, together with improved lower bounds. 
Finally, we extend graph motif parameters to colored subgraphs and prove a complexity trichotomy: For vertex-colored graphs H and G, where H is from a fixed class , we want to count color-preserving H-copies in G. We show that this problem is either polynomial-time solvable or FPT or #W[1]-hard, and that the FPT cases indeed need FPT time under reasonable assumptions.
]]></description>
<dc:subject>graph-theory feature-construction computational-complexity algorithms rather-interesting heuristics to-write-about to-simulate consider:representation consider:slow-algorithms-but-obvious</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:47778c23cce3/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:heuristics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:slow-algorithms-but-obvious"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1604.01282">
    <title>[1604.01282] New Bounds for Facial Nonrepetitive Colouring</title>
    <dc:date>2020-05-18T21:58:41+00:00</dc:date>
    <link>https://arxiv.org/abs/1604.01282</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We prove that the facial nonrepetitive chromatic number of any outerplanar graph is at most 11 and of any planar graph is at most 22.
]]></description>
<dc:subject>graph-theory graph-coloring feature-construction rather-odd to-understand to-simulate consider:looking-to-see consider:permutations</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:f59aa2a2efe5/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-coloring"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-odd"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:permutations"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1610.02107">
    <title>[1610.02107] Edges and Vertices in a Unique Signed Circle in a Signed Graph</title>
    <dc:date>2020-05-18T21:44:50+00:00</dc:date>
    <link>https://arxiv.org/abs/1610.02107</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We examine the conditions under which a signed graph contains an edge or a vertex that is contained in a unique negative circle or a unique positive circle. For an edge in a unique signed circle, the positive and negative case require the same structure on the underlying graph, but the requirements on the signature are different. We characterize the structure of the underlying graph necessary to support such an edge in terms of bridges of a circle. We then use the results from the edge version of the problem to help solve the vertex version.
]]></description>
<dc:subject>graph-theory feature-construction rather-interesting consider:assignment to-simulate consider:feature-discovery</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:86e5ec6493af/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:assignment"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:feature-discovery"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1804.02075">
    <title>[1804.02075] A Framework for Searching in Graphs in the Presence of Errors</title>
    <dc:date>2020-05-17T22:22:25+00:00</dc:date>
    <link>https://arxiv.org/abs/1804.02075</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We consider the problem of searching for an unknown target vertex t in a (possibly edge-weighted) graph. Each \emph{vertex-query} points to a vertex v and the response either admits v is the target or provides any neighbor s≠v that lies on a shortest path from v to t. This model has been introduced for trees by Onak and Parys [FOCS 2006] and for general graphs by Emamjomeh-Zadeh et al. [STOC 2016]. In the latter, the authors provide algorithms for the error-less case and for the independent noise model (where each query independently receives an erroneous answer with known probability p<1/2 and a correct one with probability 1−p). 
We study this problem in both adversarial errors and independent noise models. First, we show an algorithm that needs log2n1−H(r) queries against \emph{adversarial} errors, where adversary is bounded with its rate of errors by a known constant r<1/2. Our algorithm is in fact a simplification of previous work, and our refinement lies in invoking amortization argument. We then show that our algorithm coupled with Chernoff bound argument leads to an algorithm for independent noise that is simpler and with a query complexity that is both simpler and asymptotically better to one of Emamjomeh-Zadeh et al. [STOC 2016]. 
Our approach has a wide range of applications. First, it improves and simplifies Robust Interactive Learning framework proposed by Emamjomeh-Zadeh et al. [NIPS 2017]. Secondly, performing analogous analysis for \emph{edge-queries} (where query to edge e returns its endpoint that is closer to target) we actually recover (as a special case) noisy binary search algorithm that is asymptotically optimal, matching the complexity of Feige et al. [SIAM J. Comput. 1994]. Thirdly, we improve and simplify upon existing algorithm for searching of \emph{unbounded} domains due to Aslam and Dhagat [STOC 1991].
]]></description>
<dc:subject>graph-theory algorithms robustness error-correction rather-interesting to-write-about computational-complexity to-simulate consider:graph-structure</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:b450a0214352/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:robustness"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:error-correction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:graph-structure"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1904.04341">
    <title>[1904.04341] Distributed Edge Connectivity in Sublinear Time</title>
    <dc:date>2020-05-16T12:22:20+00:00</dc:date>
    <link>https://arxiv.org/abs/1904.04341</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We present the first sublinear-time algorithm for a distributed message-passing network sto compute its edge connectivity λ exactly in the CONGEST model, as long as there are no parallel edges. Our algorithm takes Õ(n1−1/353D1/353+n1−1/706) time to compute λ and a cut of cardinality λ with high probability, where n and D are the number of nodes and the diameter of the network, respectively, and Õ hides polylogarithmic factors. This running time is sublinear in n (i.e. Õ(n1−ϵ)) whenever D is. Previous sublinear-time distributed algorithms can solve this problem either (i) exactly only when λ=O(n1/8−ϵ) [Thurimella PODC'95; Pritchard, Thurimella, ACM Trans. Algorithms'11; Nanongkai, Su, DISC'14] or (ii) approximately [Ghaffari, Kuhn, DISC'13; Nanongkai, Su, DISC'14]. 
To achieve this we develop and combine several new techniques. First, we design the first distributed algorithm that can compute a k-edge connectivity certificate for any k=O(n1−ϵ) in time Õ(nk‾‾‾√+D). Second, we show that by combining the recent distributed expander decomposition technique of [Chang, Pettie, Zhang, SODA'19] with techniques from the sequential deterministic edge connectivity algorithm of [Kawarabayashi, Thorup, STOC'15], we can decompose the network into a sublinear number of clusters with small average diameter and without any mincut separating a cluster (except the `trivial' ones). Finally, by extending the tree packing technique from [Karger STOC'96], we can find the minimum cut in time proportional to the number of components. As a byproduct of this technique, we obtain an Õ(n)-time algorithm for computing exact minimum cut for weighted graphs.
]]></description>
<dc:subject>computational-complexity graph-theory algorithms distributed-processing rather-interesting to-understand to-write-about consider:looking-to-see consider:genetic-programming consider:cellular-automata</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:73e069c312bd/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:computational-complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:algorithms"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:distributed-processing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-understand"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:genetic-programming"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:cellular-automata"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1710.08486">
    <title>[1710.08486] Decomposing graphs into edges and triangles</title>
    <dc:date>2020-05-16T12:14:07+00:00</dc:date>
    <link>https://arxiv.org/abs/1710.08486</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[We prove the following 30-year old conjecture of Győri and Tuza: the edges of every n-vertex graph G can be decomposed into complete graphs C1,…,Cℓ of orders two and three such that |C1|+⋯+|Cℓ|≤(1/2+o(1))n2. This result implies the asymptotic version of the old result of Erdős, Goodman and Pósa that asserts the existence of such a decomposition with ℓ≤n2/4.
]]></description>
<dc:subject>graph-theory combinatorics feature-construction proof to-simulate to-write-about consider:looking-to-see consider:sampling</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:f4f7a5aaa115/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:proof"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:looking-to-see"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:sampling"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/math/0608422">
    <title>[math/0608422] Boundary Partitions in Trees and Dimers</title>
    <dc:date>2020-05-16T11:54:25+00:00</dc:date>
    <link>https://arxiv.org/abs/math/0608422</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[Given a finite planar graph, a grove is a spanning forest in which every component tree contains one or more of a specified set of vertices (called nodes) on the outer face. For the uniform measure on groves, we compute the probabilities of the different possible node connections in a grove. These probabilities only depend on boundary measurements of the graph and not on the actual graph structure, i.e., the probabilities can be expressed as functions of the pairwise electrical resistances between the nodes, or equivalently, as functions of the Dirichlet-to-Neumann operator (or response matrix) on the nodes. These formulae can be likened to generalizations (for spanning forests) of Cardy's percolation crossing probabilities, and generalize Kirchhoff's formula for the electrical resistance. Remarkably, when appropriately normalized, the connection probabilities are in fact integer-coefficient polynomials in the matrix entries, where the coefficients have a natural algebraic interpretation and can be computed combinatorially. A similar phenomenon holds in the so-called double-dimer model: connection probabilities of boundary nodes are polynomial functions of certain boundary measurements, and as formal polynomials, they are specializations of the grove polynomials. Upon taking scaling limits, we show that the double-dimer connection probabilities coincide with those of the contour lines in the Gaussian free field with certain natural boundary conditions. These results have direct application to connection probabilities for multiple-strand SLE_2, SLE_8, and SLE_4.
]]></description>
<dc:subject>domino-tiling graph-theory graph-layout combinatorics enumeration feature-construction rather-interesting to-write-about to-simulate consider:heuristics consider:algorithms</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:912a1fb47b1b/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:domino-tiling"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-layout"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:enumeration"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:heuristics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:algorithms"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1904.05269">
    <title>[1904.05269] Planar graphs have bounded nonrepetitive chromatic number</title>
    <dc:date>2020-05-14T13:41:49+00:00</dc:date>
    <link>https://arxiv.org/abs/1904.05269</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[A colouring of a graph is "nonrepetitive" if for every path of even order, the sequence of colours on the first half of the path is different from the sequence of colours on the second half. We show that planar graphs have nonrepetitive colourings with a bounded number of colours, thus proving a conjecture of Alon, Grytczuk, Haluszczak and Riordan (2002). We also generalise this result for graphs of bounded Euler genus, graphs excluding a fixed minor, and graphs excluding a fixed topological minor.
]]></description>
<dc:subject>graph-theory feature-construction combinatorics constraint-satisfaction rather-interesting to-simulate to-write-about consider:rediscovery</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:abbe029b45c0/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:feature-construction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:constraint-satisfaction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:rediscovery"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1903.06012">
    <title>[1903.06012] Point-ellipse and some other exotic configurations</title>
    <dc:date>2020-05-14T01:01:37+00:00</dc:date>
    <link>https://arxiv.org/abs/1903.06012</link>
    <dc:creator>Vaguery</dc:creator><description><![CDATA[In this paper we introduce point-ellipse configurations and point-conic configurations. We study some of their basic properties and describe two interesting families of balanced point-ellipse, respectively point-conic 6-configurations. The construction of the first family is based on Carnot's theorem, whilst the construction of the second family is based on the Cartesian product of two regular polygons. Finally, we investigate a point-ellipse configuration based on the regular 24-cell.
]]></description>
<dc:subject>geometric-graphs graph-theory graph-layout rather-interesting to-simulate combinatorics enumeration to-write-about consider:eccentricity consider:genetic-programming consider:representation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:Vaguery/b:c635ac4daf6f/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:geometric-graphs"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:graph-layout"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:rather-interesting"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-simulate"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:combinatorics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:enumeration"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:to-write-about"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:eccentricity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:genetic-programming"/>
	<rdf:li rdf:resource="https://pinboard.in/u:Vaguery/t:consider:representation"/>
</rdf:Bag></taxo:topics>
</item>
</rdf:RDF>