Lecture 20 - Discrete Mathematics, Virtual University of Pakistan by Dr. Shoaib-ud-Din

Topics: MTH202, Discrete Mathematics, Dr. Shoaib-ud-Din

50
50

Nov 19, 2020
11/20

by
Abdzex_Kuban

texts

######
eye 50

######
favorite 0

######
comment 0

Graph Theory Discrete Mathematics And Optimization

Topic: Graph Theory Discrete Mathematics And Optimization

6
6.0

Jun 29, 2018
06/18

by
Tony Huynh; Peter Nelson

texts

######
eye 6

######
favorite 0

######
comment 0

We prove that for every proper minor-closed class $M$ of matroids representable over a prime field, there exists a constant-competitive matroid secretary algorithm for the matroids in $M$. This result relies on the extremely powerful matroid minor structure theory being developed by Geelen, Gerards and Whittle. We also note that for asymptotically almost all matroids, the matroid secretary algorithm that selects a random basis, ignoring weights, is $(2+o(1))$-competitive. In fact, assuming the...

Topics: Combinatorics, Discrete Mathematics, Computing Research Repository, Mathematics

Source: http://arxiv.org/abs/1603.06822

3
3.0

Jun 30, 2018
06/18

by
Arijit Bishnu; Kunal Dutta; Arijit Ghosh; Subhabrata Paul

texts

######
eye 3

######
favorite 0

######
comment 0

A subset $D \subseteq V $of a graph $G = (V, E)$ is a $(1, j)$-set if every vertex $v \in V \setminus D$ is adjacent to at least $1$ but not more than $j$ vertices in D. The cardinality of a minimum $(1, j)$-set of $G$, denoted as $\gamma_{(1,j)} (G)$, is called the $(1, j)$-domination number of $G$. Given a graph $G = (V, E)$ and an integer $k$, the decision version of the $(1, j)$-set problem is to decide whether $G$ has a $(1, j)$-set of cardinality at most $k$. In this paper, we first...

Topics: Mathematics, Discrete Mathematics, Computing Research Repository, Combinatorics

Source: http://arxiv.org/abs/1410.3091

3
3.0

Jun 28, 2018
06/18

by
Ryan O'Donnell; Yu Zhao

texts

######
eye 3

######
favorite 0

######
comment 0

Let f(x) = f(x_1, ..., x_n) = \sum_{|S|

Topics: Probability, Discrete Mathematics, Computing Research Repository, Mathematics

Source: http://arxiv.org/abs/1512.01603

2
2.0

Jun 30, 2018
06/18

by
Michael Hochman; Pascal Vanier

texts

######
eye 2

######
favorite 0

######
comment 0

Subshifts are shift invariant closed subsets of $\Sigma^{\mathbb{Z}^d}$ , minimal subshifts are subshifts in which all points contain the same patterns. It has been proved by Jeandel and Vanier that the Turing degree spectra of non-periodic minimal subshifts always contain the cone of Turing degrees above any of its degree. It was however not known whether each minimal subshift's spectrum was formed of exactly one cone or not. We construct inductively a minimal subshift whose spectrum consists...

Topics: Discrete Mathematics, Computing Research Repository, Logic in Computer Science, Formal Languages...

Source: http://arxiv.org/abs/1408.6487

3
3.0

Jun 30, 2018
06/18

by
Marina Groshaus; André Guedes; Leandro Montero

texts

######
eye 3

######
favorite 0

######
comment 0

A biclique of a graph $G$ is a maximal induced complete bipartite subgraph of $G$. The biclique graph of $G$ denoted by $KB(G)$, is the intersection graph of all the bicliques of $G$. The biclique graph can be thought as an operator between graphs. The iterated biclique graph of $G$ denoted by $KB^{k}(G)$, is the graph obtained by applying the biclique operator $k$ successive times to $G$. The associated problem is deciding whether an input graph converges, diverges or is periodic under the...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1408.6063

3
3.0

Jun 30, 2018
06/18

by
Nicolas Bédaride; Thomas Fernique

texts

######
eye 3

######
favorite 0

######
comment 0

On the one hand, Socolar showed in 1990 that the n-fold planar tilings admit weak local rules when n is not divisible by 4 (the n=10 case corresponds to the Penrose tilings and is known since 1974). On the other hand, Burkov showed in 1988 that the 8-fold tilings do not admit weak local rules, and Le showed the same for the 12-fold tilings (unpublished). We here show that this is actually the case for all the 4p-fold tilings.

Topics: Mathematics, Discrete Mathematics, Computing Research Repository, Mathematical Physics, Dynamical...

Source: http://arxiv.org/abs/1409.0215

3
3.0

Jun 30, 2018
06/18

by
Ashwin Ganesan

texts

######
eye 3

######
favorite 0

######
comment 0

The modified bubble-sort graph of dimension $n$ is the Cayley graph of $S_n$ generated by $n$ cyclically adjacent transpositions. In the present paper, it is shown that the automorphism group of the modified bubble sort graph of dimension $n$ is $S_n \times D_{2n}$, for all $n \ge 5$. Thus, a complete structural description of the automorphism group of the modified bubble-sort graph is obtained. A similar direct product decomposition is seen to hold for arbitrary normal Cayley graphs generated...

Topics: Mathematics, Discrete Mathematics, Combinatorics, Computing Research Repository, Group Theory

Source: http://arxiv.org/abs/1409.5959

3
3.0

Jun 30, 2018
06/18

by
Jun Zhao; Osman Yağan; Virgil Gligor

texts

######
eye 3

######
favorite 0

######
comment 0

Random intersection graphs have received much attention for nearly two decades, and currently have a wide range of applications ranging from key predistribution in wireless sensor networks to modeling social networks. In this paper, we investigate the strengths of connectivity and robustness in a general random intersection graph model. Specifically, we establish sharp asymptotic zero-one laws for $k$-connectivity and $k$-robustness, as well as the asymptotically exact probability of...

Topics: Physics, Combinatorics, Mathematics, Discrete Mathematics, Computing Research Repository, Physics...

Source: http://arxiv.org/abs/1409.5995

2
2.0

Jun 30, 2018
06/18

by
Maximilien Gadouleau; Adrien Richard; Søren Riis

texts

######
eye 2

######
favorite 0

######
comment 0

In this paper, we are interested in the number of fixed points of functions $f:A^n\to A^n$ over a finite alphabet $A$ defined on a given signed digraph $D$. We first use techniques from network coding to derive some lower bounds on the number of fixed points that only depends on $D$. We then discover relationships between the number of fixed points of $f$ and problems in coding theory, especially the design of codes for the asymmetric channel. Using these relationships, we derive upper and...

Topics: Mathematics, Discrete Mathematics, Computing Research Repository, Information Theory, Dynamical...

Source: http://arxiv.org/abs/1409.6144

3
3.0

Jun 30, 2018
06/18

by
Giuseppe Di Battista; Fabrizio Frati

texts

######
eye 3

######
favorite 0

######
comment 0

We survey algorithms and bounds for constructing planar drawings of graphs in small area.

Topics: Discrete Mathematics, Computing Research Repository, Computational Geometry, Data Structures and...

Source: http://arxiv.org/abs/1410.1006

2
2.0

Jun 30, 2018
06/18

by
Jakub Kozik; Grzegorz Matecki

texts

######
eye 2

######
favorite 0

######
comment 0

We present a new approach, called a lazy matching, to the problem of on-line matching on bipartite graphs. Imagine that one side of a graph is given and the vertices of the other side are arriving on-line. Originally, incoming vertex is either irrevocably matched to an another element or stays forever unmatched. A lazy algorithm is allowed to match a new vertex to a group of elements (possibly empty) and afterwords, forced against next vertices, may give up parts of the group. The restriction...

Topics: Discrete Mathematics, Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1410.3764

4
4.0

Jun 30, 2018
06/18

by
Petruţ Cobârzan

texts

######
eye 4

######
favorite 0

######
comment 0

We consider here on-line algorithms for Achlioptas processes. Given a initially empty graph $G$ on $n$ vertices, a random process that at each step selects independently and uniformly at random two edges from the set of non-edges is launched. We must choose one of the two edges and add it to the graph while discarding the other. The goal is to avoid the appearance of a connected component spanning $\Omega(n)$ vertices (called a giant component) for as many steps as possible. Bohman and Frieze...

Topics: Mathematics, Discrete Mathematics, Computing Research Repository, Combinatorics

Source: http://arxiv.org/abs/1410.3876

2
2.0

Jun 30, 2018
06/18

by
S. Bianchi; M. Escalante; G. Nasini; L. Tunçel

texts

######
eye 2

######
favorite 0

######
comment 0

We study the Lov\'asz-Schrijver lift-and-project operator ($LS_+$) based on the cone of symmetric, positive semidefinite matrices, applied to the fractional stable set polytope of graphs. The problem of obtaining a combinatorial characterization of graphs for which the $LS_+$-operator generates the stable set polytope in one step has been open since 1990. We call these graphs $LS_+$-perfect. In the current contribution, we pursue a full combinatorial characterization of $LS_+$-perfect graphs...

Topics: Mathematics, Discrete Mathematics, Computing Research Repository, Optimization and Control

Source: http://arxiv.org/abs/1411.2069

2
2.0

Jun 30, 2018
06/18

by
Jarkko Peltomäki

texts

######
eye 2

######
favorite 0

######
comment 0

We present a new, dynamical way to study powers (that is, repetitions) in Sturmian words based on results from Diophantine approximation theory. As a result, we provide an alternative and shorter proof of a result by Damanik and Lenz characterizing powers in Sturmian words [Powers in Sturmian sequences, Eur. J. Combin. 24 (2003), 377--390]. Further, as a consequence, we obtain a previously known formula for the fractional index of a Sturmian word based on the continued fraction expansion of its...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1411.5474

2
2.0

Jun 30, 2018
06/18

by
Isabel Méndez Díaz; Graciela Nasini; Daniel Severín

texts

######
eye 2

######
favorite 0

######
comment 0

The Equitable Coloring Problem is a variant of the Graph Coloring Problem where the sizes of two arbitrary color classes differ in at most one unit. This additional condition, called equity constraints, arises naturally in several applications. Due to the hardness of the problem, current exact algorithms can not solve large-sized instances. Such instances must be addressed only via heuristic methods. In this paper we present a tabu search heuristic for the Equitable Coloring Problem. This...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1405.7020

2
2.0

Jun 30, 2018
06/18

by
Nicola Apollonio; Massimiliano Caramia; Paolo Giulio Franciosa

texts

######
eye 2

######
favorite 0

######
comment 0

We give a complete characterization of bipartite graphs having tree-like Galois lattices. We prove that the poset obtained by deleting bottom and top elements from the Galois lattice of a bipartite graph is tree-like if and only if the graph is a Bipartite Distance Hereditary graph. By relying on the interplay between bipartite distance hereditary graphs and series-parallel graphs, we show that the lattice can be realized as the containment relation among directed paths in an arborescence....

Topics: Mathematics, Discrete Mathematics, Computing Research Repository, Combinatorics

Source: http://arxiv.org/abs/1406.0154

2
2.0

Jun 30, 2018
06/18

by
Nilanjan De; Anita Pal; Sk. Md. Abu Nayeem

texts

######
eye 2

######
favorite 0

######
comment 0

The connective eccentric index of a graph is a topological index involving degrees and eccentricities of vertices of the graph. In this paper, we have studied the connective eccentric index for double graph and double cover. Also we give the connective eccentric index for some graph operations such as joins, symmetric difference, disjunction and splice of graphs.

Topics: Mathematics, Discrete Mathematics, Combinatorics, Computing Research Repository

Source: http://arxiv.org/abs/1406.0378

4
4.0

Jun 30, 2018
06/18

by
Charilaos Efthymiou

texts

######
eye 4

######
favorite 0

######
comment 0

The broadcasting models on trees arise in many contexts such as discrete mathematics, biology statistical physics and cs. In this work, we consider the colouring model. A basic question here is whether the root's assignment affects the distribution of the colourings at the vertices at distance h from the root. This is the so-called "reconstruction problem". For a d-ary tree it is well known that d/ln (d) is the reconstruction threshold. That is, for k=(1+eps)d/ln(d) we have...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1406.3617

2
2.0

Jun 30, 2018
06/18

by
Arturo Carpi; Gabriele Fici; Stepan Holub; Jakub Oprsal; Marinella Sciortino

texts

######
eye 2

######
favorite 0

######
comment 0

A word $w$ over an alphabet $\Sigma$ is a Lyndon word if there exists an order defined on $\Sigma$ for which $w$ is lexicographically smaller than all of its conjugates (other than itself). We introduce and study \emph{universal Lyndon words}, which are words over an $n$-letter alphabet that have length $n!$ and such that all the conjugates are Lyndon words. We show that universal Lyndon words exist for every $n$ and exhibit combinatorial and structural properties of these words. We then define...

Topics: Mathematics, Discrete Mathematics, Computing Research Repository, Combinatorics, Formal Languages...

Source: http://arxiv.org/abs/1406.5895

3
3.0

Jun 30, 2018
06/18

by
Liam Roditty; Roei Tov

texts

######
eye 3

######
favorite 0

######
comment 0

Let $G=(V,E)$ be an undirected graph with $n$ vertices and $m$ edges. We obtain the following new routing schemes: - A routing scheme for unweighted graphs that uses $\tilde O(\frac{1}{\epsilon} n^{2/3})$ space at each vertex and $\tilde O(1/\epsilon)$-bit headers, to route a message between any pair of vertices $u,v\in V$ on a $(2 + \epsilon,1)$-stretch path, i.e., a path of length at most $(2+\epsilon)\cdot d(u,v)+1$. This should be compared to the $(2,1)$-stretch and $\tilde O(n^{5/3})$...

Topics: Discrete Mathematics, Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1407.6730

2
2.0

Jun 30, 2018
06/18

by
Oliver Kullmann; Xishun Zhao

texts

######
eye 2

######
favorite 0

######
comment 0

We investigate connections between SAT (the propositional satisfiability problem) and combinatorics, around the minimum degree (number of occurrences) of variables in various forms of redundancy-free boolean conjunctive normal forms (clause-sets). Lean clause-sets do not have non-trivial autarkies, that is, it is not possible to satisfy some clauses and leave the other clauses untouched. The deficiency of a clause-set is the difference of the number of clauses and the number of variables. We...

Topics: Mathematics, Discrete Mathematics, Combinatorics, Computing Research Repository, Logic in Computer...

Source: http://arxiv.org/abs/1408.0629

3
3.0

Jun 30, 2018
06/18

by
Eglantine Camby; Oliver Schaudt

texts

######
eye 3

######
favorite 0

######
comment 0

The class of graphs that do not contain an induced path on $k$ vertices, $P_k$-free graphs, plays a prominent role in algorithmic graph theory. This motivates the search for special structural properties of $P_k$-free graphs, including alternative characterizations. Let $G$ be a connected $P_k$-free graph, $k \ge 4$. We show that $G$ admits a connected dominating set whose induced subgraph is either $P_{k-2}$-free, or isomorphic to $P_{k-2}$. Surprisingly, it turns out that every minimum...

Topics: Mathematics, Discrete Mathematics, Computing Research Repository, Combinatorics

Source: http://arxiv.org/abs/1402.7213

2
2.0

Jun 30, 2018
06/18

by
Akira Matsubayashi

texts

######
eye 2

######
favorite 0

######
comment 0

We study the problem of embedding a guest graph with minimum edge-congestion into a multidimensional grid with the same size as that of the guest graph. Based on a well-known notion of graph separators, we show that an embedding with a smaller edge-congestion can be obtained if the guest graph has a smaller separator, and if the host grid has a higher but constant dimension. Specifically, we prove that any graph with $N$ nodes, maximum node degree $\Delta$, and with a node-separator of size...

Topics: Mathematics, Discrete Mathematics, Computing Research Repository, Combinatorics

Source: http://arxiv.org/abs/1402.7293

3
3.0

Jun 30, 2018
06/18

by
Konrad K. Dabrowski; Daniël Paulusma

texts

######
eye 3

######
favorite 0

######
comment 0

Let $G$ be a bipartite graph, and let $H$ be a bipartite graph with a fixed bipartition $(B_H,W_H)$. We consider three different, natural ways of forbidding $H$ as an induced subgraph in $G$. First, $G$ is $H$-free if it does not contain $H$ as an induced subgraph. Second, $G$ is strongly $H$-free if $G$ is $H$-free or else has no bipartition $(B_G,W_G)$ with $B_H\subseteq B_G$ and $W_H\subseteq W_G$. Third, $G$ is weakly $H$-free if $G$ is $H$-free or else has at least one bipartition...

Topics: Mathematics, Discrete Mathematics, Computing Research Repository, Combinatorics

Source: http://arxiv.org/abs/1402.7060

2
2.0

Jun 30, 2018
06/18

by
Michael Codish; Michael Frank; Avraham Itzhakov; Alice Miller

texts

######
eye 2

######
favorite 0

######
comment 0

This paper introduces a general methodology, based on abstraction and symmetry, that applies to solve hard graph edge-coloring problems and demonstrates its use to provide further evidence that the Ramsey number $R(4,3,3)=30$. The number $R(4,3,3)$ is often presented as the unknown Ramsey number with the best chances of being found "soon". Yet, its precise value has remained unknown for more than 50 years. We illustrate our approach by showing that: (1) there are precisely 78{,}892...

Topics: Discrete Mathematics, Computing Research Repository, Artificial Intelligence

Source: http://arxiv.org/abs/1409.5189

2
2.0

Jun 30, 2018
06/18

by
Anthony Bonato; Marc Lozier; Dieter Mitsche; Xavier Pérez-Giménez; Paweł Prałat

texts

######
eye 2

######
favorite 0

######
comment 0

We consider the domination number for on-line social networks, both in a stochastic network model, and for real-world, networked data. Asymptotic sublinear bounds are rigorously derived for the domination number of graphs generated by the memoryless geometric protean random graph model. We establish sublinear bounds for the domination number of graphs in the Facebook 100 data set, and these bounds are well-correlated with those predicted by the stochastic model. In addition, we derive the...

Topics: Discrete Mathematics, Computing Research Repository, Social and Information Networks

Source: http://arxiv.org/abs/1412.1189

3
3.0

Jun 30, 2018
06/18

by
Neal Lawton

texts

######
eye 3

######
favorite 0

######
comment 0

In this paper we modify an algorithm for updating a maximal clique enumeration after an edge insertion to provide an algorithm that runs in linear time with respect to the number of cliques containing one of the edge's endpoints, whereas existing algorithms take quadratic time.

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1412.4620

2
2.0

Jun 30, 2018
06/18

by
Marthe Bonamy; Hervé Hocquard; Samia Kerdjoudj; André Raspaud

texts

######
eye 2

######
favorite 0

######
comment 0

An incidence of an undirected graph G is a pair $(v,e)$ where $v$ is a vertex of $G$ and $e$ an edge of $G$ incident with $v$. Two incidences $(v,e)$ and $(w,f)$ are adjacent if one of the following holds: (i) $v = w$, (ii) $e = f$ or (iii) $vw = e$ or $f$. An incidence coloring of $G$ assigns a color to each incidence of $G$ in such a way that adjacent incidences get distinct colors. In 2005, Hosseini Dolama \emph{et al.}~\citep{ds05} proved that every graph with maximum average degree...

Topics: Mathematics, Discrete Mathematics, Computing Research Repository, Combinatorics

Source: http://arxiv.org/abs/1412.6803

3
3.0

Jun 30, 2018
06/18

by
V. Ch. Venkaiah; K. Ramanjaneyulu; Neelima Jampala; J. Rajendra Prasad

texts

######
eye 3

######
favorite 0

######
comment 0

Let c(F) be the number of perfect pairs of F and c(G) be the maximum of c(F) over all (near-) one-factorizations F of G. Wagner showed that for odd n, c(K_{n}) \geq n*phi(n)/2 and for m and n which are odd and co-prime to each other, c(K_{mn}) \geq 2*c(K_{m})*c(K_{n}). In this note, we establish that both these results are equivalent in the sense that they both give rise to the same lower bound.

Topics: Mathematics, Discrete Mathematics, Computing Research Repository, Combinatorics

Source: http://arxiv.org/abs/1412.6793

2
2.0

Jun 30, 2018
06/18

by
Satoru Iwata; Naoyuki Kamiyama; Naoki Katoh; Shuji Kijima; Yoshio Okamoto

texts

######
eye 2

######
favorite 0

######
comment 0

We show the existence of a polynomial-size extended formulation for the base polytope of a $(k,\ell)$-sparsity matroid. For an undirected graph $G=(V,E)$, the size of the formulation is $O(|V||E|)$ when $k \geq \ell$ and $O(|V|^2 |E|)$ when $k \leq \ell$. To this end, we employ the technique developed by Faenza et al. recently that uses a randomized communication protocol.

Topics: Mathematics, Discrete Mathematics, Combinatorics, Computing Research Repository, Optimization and...

Source: http://arxiv.org/abs/1403.7272

3
3.0

Jun 30, 2018
06/18

by
Pablo Arrighi; Simon Martiel; Zizhu Wang

texts

######
eye 3

######
favorite 0

######
comment 0

We formalize the intuitive idea of a labelled discrete surface which evolves in time, subject to two natural constraints: the evolution does not propagate information too fast; and it acts everywhere the same.

Topics: Discrete Mathematics, Computing Research Repository, Computational Geometry

Source: http://arxiv.org/abs/1404.0083

2
2.0

Jun 30, 2018
06/18

by
Mustafa Khandwawala

texts

######
eye 2

######
favorite 0

######
comment 0

In a complete bipartite graph with vertex sets of cardinalities $n$ and $m$, assign random weights from exponential distribution with mean 1, independently to each edge. We show that, as $n\rightarrow\infty$, with $m = \lceil n/\alpha\rceil$ for any fixed $\alpha>1$, the minimum weight of many-to-one matchings converges to a constant (depending on $\alpha$). Many-to-one matching arises as an optimization step in an algorithm for genome sequencing and as a measure of distance between finite...

Topics: Probability, Mathematics, Discrete Mathematics, Computing Research Repository, Information Theory

Source: http://arxiv.org/abs/1405.1292

2
2.0

Jun 30, 2018
06/18

by
Ali Pourmiri

texts

######
eye 2

######
favorite 0

######
comment 0

In this paper we propose algorithms for allocating $n$ sequential balls into $n$ bins that are interconnected as a $d$-regular $n$-vertex graph $G$, where $d\ge3$ can be any integer.Let $l$ be a given positive integer. In each round $t$, $1\le t\le n$, ball $t$ picks a node of $G$ uniformly at random and performs a non-backtracking random walk of length $l$ from the chosen node.Then it allocates itself on one of the visited nodes with minimum load (ties are broken uniformly at random). Suppose...

Topics: Probability, Mathematics, Discrete Mathematics, Data Structures and Algorithms, Computing Research...

Source: http://arxiv.org/abs/1407.2575

2
2.0

Jun 30, 2018
06/18

by
Alexander Yu. Vlasov

texts

######
eye 2

######
favorite 0

######
comment 0

Recursive equations for the number of cells with nonzero values at $n$-th step for some two-dimensional reversible second-order cellular automata are proved in this work. Initial configuration is a single cell with the value one and all others zero.

Topics: Nonlinear Sciences, Combinatorics, Mathematics, Discrete Mathematics, Computing Research...

Source: http://arxiv.org/abs/1407.6553

2
2.0

Jun 30, 2018
06/18

by
Viet Hang Nguyen

texts

######
eye 2

######
favorite 0

######
comment 0

We show that if $G$ is a connected graph of maximum degree at most $4$, which is not $C_{2,5}$, then the strong matching number of $G$ is at least $\frac{1}{9}n(G)$. This bound is tight and the proof implies a polynomial time algorithm to find an induced matching of this size.

Topics: Mathematics, Discrete Mathematics, Computing Research Repository, Combinatorics

Source: http://arxiv.org/abs/1407.7604

2
2.0

Jun 30, 2018
06/18

by
Cameron T. Chalk; Dominic A. Fernandez; Alejandro Huerta; Mario A. Maldonado; Robert T. Schweller; Leslie Sweet

texts

######
eye 2

######
favorite 0

######
comment 0

In this paper we consider the problem of the strict self-assembly of infinite fractals within tile self-assembly. In particular, we provide tile assembly algorithms for the assembly of the discrete Sierpinski triangle and the discrete Sierpinski carpet within a class of models we term the \emph{$h$-handed assembly model} ($h$-HAM), which generalizes the 2-HAM to allow up to $h$ assemblies to combine in a single assembly step. Despite substantial consideration, no purely growth self-assembly...

Topics: Discrete Mathematics, Computing Research Repository, Computational Geometry

Source: http://arxiv.org/abs/1407.7900

3
3.0

Jun 30, 2018
06/18

by
Markus Chimani; Giuseppe Di Battista; Fabrizio Frati; Karsten Klein

texts

######
eye 3

######
favorite 0

######
comment 0

We show a polynomial-time algorithm for testing c-planarity of embedded flat clustered graphs with at most two vertices per cluster on each face.

Topics: Discrete Mathematics, Data Structures and Algorithms, Computing Research Repository, Computational...

Source: http://arxiv.org/abs/1408.2595

3
3.0

Jun 30, 2018
06/18

by
Hooman Reisi Dehkordi; Fabrizio Frati; Joachim Gudmundsson

texts

######
eye 3

######
favorite 0

######
comment 0

We tackle the problem of constructing increasing-chord graphs spanning point sets. We prove that, for every point set P with n points, there exists an increasing-chord planar graph with O(n) Steiner points spanning P. Further, we prove that, for every convex point set P with n points, there exists an increasing-chord graph with O(n log n) edges (and with no Steiner points) spanning P.

Topics: Discrete Mathematics, Computing Research Repository, Computational Geometry

Source: http://arxiv.org/abs/1408.2592

2
2.0

Jun 30, 2018
06/18

by
Mathew Francis; Pavol Hell; Juraj Stacho

texts

######
eye 2

######
favorite 0

######
comment 0

A circular-arc graph is the intersection graph of arcs of a circle. It is a well-studied graph model with numerous natural applications. A certifying algorithm is an algorithm that outputs a certificate, along with its answer (be it positive or negative), where the certificate can be used to easily justify the given answer. While the recognition of circular-arc graphs has been known to be polynomial since the 1980s, no polynomial-time certifying recognition algorithm is known to date, despite...

Topics: Mathematics, Discrete Mathematics, Computing Research Repository, Combinatorics

Source: http://arxiv.org/abs/1408.2639

10
10.0

Jun 30, 2018
06/18

by
Shmuel Onn

texts

######
eye 10

######
favorite 0

######
comment 0

We provide a complexity classification of four variants of robust integer programming when the underlying Graver basis is given. We discuss applications to robust multicommodity flows and multidimensional transportation, and describe an effective parametrization of robust integer programming.

Topics: Combinatorics, Mathematics, Discrete Mathematics, Computing Research Repository, Data Structures...

Source: http://arxiv.org/abs/1402.2852

2
2.0

Jun 30, 2018
06/18

by
Klaus Wehmuth; Artur Ziviani; Eric Fleury

texts

######
eye 2

######
favorite 0

######
comment 0

Graph-based models form a fundamental aspect of data representation in Data Sciences and play a key role in modeling complex networked systems. In particular, recently there is an ever-increasing interest in modeling dynamic complex networks, i.e. networks in which the topological structure (nodes and edges) may vary over time. In this context, we propose a novel model for representing finite discrete Time-Varying Graphs (TVGs), which are typically used to model dynamic complex networked...

Topics: Discrete Mathematics, Data Structures and Algorithms, Computing Research Repository, Social and...

Source: http://arxiv.org/abs/1402.3488

5
5.0

Jun 30, 2018
06/18

by
Nicolas Broutin; Luc Devroye; Gábor Lugosi

texts

######
eye 5

######
favorite 0

######
comment 0

Consider a random geometric graph defined on $n$ vertices uniformly distributed in the $d$-dimensional unit torus. Two vertices are connected if their distance is less than a "visibility radius" $r_n$. We consider {\sl Bluetooth networks} that are locally sparsified random geometric graphs. Each vertex selects $c$ of its neighbors in the random geometric graph at random and connects only to the selected points. We show that if the visibility radius is at least of the order of...

Topics: Combinatorics, Mathematics, Discrete Mathematics, Computing Research Repository, Probability,...

Source: http://arxiv.org/abs/1402.3696

2
2.0

Jun 30, 2018
06/18

by
Jiří Fiala; Pavel Klavík; Jan Kratochvíl; Roman Nedela

texts

######
eye 2

######
favorite 0

######
comment 0

A graph $G$ covers a graph $H$ if there exists a locally bijective homomorphism from $G$ to $H$. We deal with regular covers in which this locally bijective homomorphism is prescribed by an action of a subgroup of ${\rm Aut}(G)$. Regular covers have many applications in constructions and studies of big objects all over mathematics and computer science. We study computational aspects of regular covers that have not been addressed before. The decision problem RegularCover asks for two given...

Topics: Mathematics, Discrete Mathematics, Combinatorics, Computing Research Repository, Data Structures...

Source: http://arxiv.org/abs/1402.3774

3
3.0

Jun 30, 2018
06/18

by
Jan Hubička; Jaroslav Nešetřil

texts

######
eye 3

######
favorite 0

######
comment 0

A bowtie is a graph consisting of two triangles with one vertex identified. We show that the class of all (countable) graphs not containing a bowtie as a subgraph have a Ramsey lift (expansion). This solves one of the old problems in the area and it is the first non-trivial Ramsey class with a non-trivial algebraic closure.

Topics: Mathematics, Discrete Mathematics, Combinatorics, Computing Research Repository

Source: http://arxiv.org/abs/1402.2700

4
4.0

Jun 30, 2018
06/18

by
Yifan Hu; Lei Shi

texts

######
eye 4

######
favorite 0

######
comment 0

Drawings of non-planar graphs always result in edge crossings. When there are many edges crossing at small angles, it is often difficult to follow these edges, because of the multiple visual paths resulted from the crossings that slow down eye movements. In this paper we propose an algorithm that disambiguates the edges with automatic selection of distinctive colors. Our proposed algorithm computes a near optimal color assignment of a dual collision graph, using a novel branch-and-bound...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1409.0436

5
5.0

Jun 29, 2018
06/18

by
Paola Flocchini; Nicola Santoro; Giovanni Viglietta; Masafumi Yamashita

texts

######
eye 5

######
favorite 0

######
comment 0

An oblivious mobile robot is a stateless computational entity located in a spatial universe, capable of moving in that universe. When activated, the robot observes the universe and the location of the other robots, chooses a destination, and moves there. The computation of the destination is made by executing an algorithm, the same for all robots, whose sole input is the current observation. No memory of all these actions is retained after the move. When the universe is a graph, distributed...

Topics: Discrete Mathematics, Distributed, Parallel, and Cluster Computing, Combinatorics, Computing...

Source: http://arxiv.org/abs/1602.04881

4
4.0

Jun 29, 2018
06/18

by
Raka Jovanovic; Islam Safak Bayram; Stefan Voss

texts

######
eye 4

######
favorite 0

######
comment 0

In this paper, we present a constructive heuristic algorithm for the $2$-connected $m$-dominating set problem. It is based on a greedy heuristic in which a 2-connected subgraph is iteratively extended with suitable open ears. The growth procedure is an adaptation of the breadth-first-search which efficiently manages to find open ears. Further, a heuristic function is defined for selecting the best ear out of a list of candidates. The performance of the basic approach is improved by adding a...

Topics: Discrete Mathematics, Computing Research Repository

Source: http://arxiv.org/abs/1609.05662

3
3.0

Jun 30, 2018
06/18

by
Marthe Bonamy; Lukasz Kowalik

texts

######
eye 3

######
favorite 0

######
comment 0

We show a kernel of at most $13k$ vertices for the Planar Feedback Vertex Set problem restricted to planar graphs, i.e., a polynomial-time algorithm that transforms an input instance $(G,k)$ to an equivalent instance with at most $13k$ vertices. To this end we introduce a few new reduction rules. However, our main contribution is an application of the region decomposition technique in the analysis of the kernel size. We show that our analysis is tight, up to a constant additive term.

Topics: Discrete Mathematics, Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1410.8336