We derive a local criterion for a plane near-triangulated graph to be
perfect. It is shown that a plane near-triangulated graph is perfect if and
only if it does not contain either a vertex, an edge or a triangle, the
neighborhood of which has an odd hole as its boundary.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 0

Unqiue Words: 0

Minimum resolution set and associated metric dimension provide the basis for
unique and systematic labeling of nodes of a graph using distances to a set of
landmarks. Such a distance vector set, however, may not be unique to the graph
and does not allow for its exact construction. The concept of construction set
is presented, which facilitates the unique representation of nodes and the
graph as well as its exact construction. Link dimension is the minimum number
of landmarks in a construction set. Results presented include necessary
conditions for a set of landmarks to be a construction set, bounds for link
dimension, and guidelines for transforming a resolution set to a construction
set.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

Milgrom (2017) has proposed a heuristic for determining a maximum weight
basis of an independence system $\mathcal I$ given that for sets from $\mathcal
O \subseteq \mathcal I$ we care in particular about the qualitiy of
approximation as we assume, that $\mathcal O$ contains (frequently) the optimal
basis. It is based on finding an `inner matroid', one contained in the
independence system. We show that without additional assumptions on $\mathcal
O$ being different from $\mathcal I$ the worst-case performance of this new
heuristic is no better than that of the classical greedy algorithm.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 5885

Unqiue Words: 1377

In this work we present a general and versatile algorithmic framework for
exhaustively generating a large variety of different combinatorial objects,
based on encoding them as permutations. This approach provides a unified view
on many known results and allows us to prove many new ones. In particular, we
obtain the following four classical Gray codes as special cases: the
Steinhaus-Johnson-Trotter algorithm to generate all permutations of an
$n$-element set by adjacent transpositions; the binary reflected Gray code to
generate all $n$-bit strings by flipping a single bit in each step; the Gray
code for generating all $n$-vertex binary trees by rotations due to Lucas, van
Baronaigien, and Ruskey; the Gray code for generating all partitions of an
$n$-element ground set by element exchanges due to Kaye. The first main
application of our framework are permutation patterns, yielding new Gray codes
for different pattern-avoiding permutations, such as vexillary, skew-merged,
separable, Baxter and twisted Baxter permutations, 2-stack...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 0

Unqiue Words: 0

We prove that the exact crossing number of a graph can be efficiently
computed for simple graphs having bounded vertex cover. In more precise words,
Crossing Number is in FPT when parameterized by the vertex cover size. This is
a notable advance since we know only very few nontrivial examples of graph
classes with unbounded and yet efficiently computable crossing number. Our
result strengthens previous result of Lokshtanov [arXiv, 2015] that Optimal
Linear Arrangement is in FPT when parameterized by the vertex cover size, and
we use a similar approach of reducing the problem to a tractable instance of
Integer Quadratic Programming as in Lokshtanov's paper.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

The generalization of De Bruijn sequences to infinite sequences with respect
to the order $n$ has been studied iand it was shown that every de Bruijn
sequence of order $n$ in at least three symbols can be extended to a de Bruijn
sequence of order $n + 1$. Every de Bruijn sequence of order $n$ in two symbols
can not be extended to order $n + 1$, but it can be extended to order $n + 2$.
A natural question to ask is if this theorem is true with respect to the
alphabet. That is, we would like to understand if we can extend a De Bruijn
sequence of order $n$ over alphabet $k$ into a into a De Bruijn sequence of
order $n$ and alphabet $k+1$. We call a De Bruijn sequence with this property
an Onion De Bruijn sequence. In this paper we show that the answer to this
question is positive. In fact, we prove that the well known Prefer Max De
Bruijn sequence has this property, and in fact every sequence with this
property behaves like the Prefer max De Bruijn sequence.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 0

Unqiue Words: 0

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

*Tracking 143,632 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible