1,882 research outputs found
Approximating the Minimum Logarithmic Arrangement Problem
Full text linkWe study a graph reordering problem motivated by compressing massive graphs such as social networks and inverted indexes. Given a graph, G = (V, E), the Minimum Logarithmic Arrangement problem is to find a permutation, π, of the vertices that minimizes ∑_{(u, v) ∈ E} (1 + ⌊ lg |π(u) - π(v)| ⌋).
This objective has been shown to be a good measure of how many bits are needed to encode the graph if the adjacency list of each vertex is encoded using relative positions of two consecutive neighbors under the π order in the list rather than using absolute indices or node identifiers, which requires at least lg n bits per edge.
We show the first non-trivial approximation factor for this problem by giving a polynomial time (log k)-approximation algorithm for graphs with treewidth k
Forbidden Patterns in Mixed Linear Layouts
Full text linkAn ordered graph is a graph with a total order over its vertices. A linear layout of an ordered graph is a partition of the edges into sets of either non-crossing edges, called stacks, or non-nesting edges, called queues. The stack (queue) number of an ordered graph is the minimum number of required stacks (queues). Mixed linear layouts combine these layouts by allowing each set of edges to form either a stack or a queue. The minimum number of stacks plus queues is called the mixed page number. It is well known that ordered graphs with small stack number are characterized, up to a function, by the absence of large twists (that is, pairwise crossing edges). Similarly, ordered graphs with small queue number are characterized by the absence of large rainbows (that is, pairwise nesting edges). However, no such characterization via forbidden patterns is known for mixed linear layouts.
We address this gap by introducing patterns similar to twists and rainbows, which we call thick patterns; such patterns allow a characterization, again up to a function, of mixed linear layouts of bounded-degree graphs. That is, we show that a family of ordered graphs with bounded maximum degree has bounded mixed page number if and only if the size of the largest thick pattern is bounded. In addition, we investigate an exact characterization of ordered graphs whose mixed page number equals a fixed integer k via a finite set of forbidden patterns. We show that for k = 2, there is no such characterization, which supports the nature of our first result
On the Extended TSP Problem
Full text linkWe initiate the theoretical study of Ext-TSP, a problem that originates in the area of profile-guided binary optimization. Given a graph G = (V, E) with positive edge weights w: E → R^+, and a non-increasing discount function f(⋅) such that f(1) = 1 and f(i) = 0 for i > k, for some parameter k that is part of the problem definition. The problem is to sequence the vertices V so as to maximize ∑_{(u, v) ∈ E} f(|d_u - d_v|)⋅ w(u,v), where d_v ∈ {1, …, |V|} is the position of vertex v in the sequence.
We show that Ext-TSP is APX-hard to approximate in general and we give a (k+1)-approximation algorithm for general graphs and a PTAS for some sparse graph classes such as planar or treewidth-bounded graphs.
Interestingly, the problem remains challenging even on very simple graph classes; indeed, there is no exact n^o(k) time algorithm for trees unless the ETH fails. We complement this negative result with an exact n^O(k) time algorithm for trees
Transforming Stacks into Queues: Mixed and Separated Layouts of Graphs
Full text linkSome of the most important open problems for linear layouts of graphs ask for the relation between a graph’s queue number and its stack number or mixed number. In such, we seek a vertex order and edge partition of G into parts with pairwise non-crossing edges (a stack) or with pairwise non-nesting edges (a queue). Allowing only stacks, only queues, or both, the minimum number of required parts is the graph’s stack number sn(G), queue number qn(G), and mixed number mn(G), respectively.
Already in 1992, Heath and Rosenberg asked whether qn(G) is bounded in terms of sn(G), that is, whether stacks "can be transformed into" queues. This is equivalent to bipartite 3-stack graphs having bounded queue number (Dujmović and Wood, 2005). Recently, Alam et al. asked whether qn(G) is bounded in terms of mn(G), which we show to also be equivalent to the previous questions.
We approach the problem by considering separated linear layouts of bipartite graphs. In this natural setting all vertices of one part must precede all vertices of the other part. Separated stack and queue numbers coincide, and for fixed vertex orders, graphs with bounded separated stack/queue number can be characterized and efficiently recognized, whereas the separated mixed layouts are more challenging. In this work, we thoroughly investigate the relationship between separated and non-separated, mixed and pure linear layouts
The Price of Upwardness
Full text linkNot every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyond planarity by considering upward k-planar drawings of DAGs in which the edges are monotonically increasing in a common direction and every edge is crossed at most k times for some integer k ≥ 1. We show that the number of crossings per edge in a monotone drawing is in general unbounded for the class of bipartite outerplanar, cubic, or bounded pathwidth DAGs. However, it is at most two for outerpaths and it is at most quadratic in the bandwidth in general. From the computational point of view, we prove that upward-k-planarity testing is NP-complete already for k = 1 and even for restricted instances for which upward planarity testing is polynomial. On the positive side, we can decide in linear time whether a single-source DAG admits an upward 1-planar drawing in which all vertices are incident to the outer face
Mixed Linear Layouts of Planar Graphs
No full textA k-stack (respectively, k-queue) layout of a graph consists of a total order of the vertices, and a partition of the edges into k sets of non-crossing (non-nested) edges with respect to the vertex ordering. In 1992, Heath and Rosenberg conjectured that every planar graph admits a mixed 1-stack 1-queue layout in which every edge is assigned to a stack or to a queue that use a common vertex ordering.
We disprove this conjecture by providing a planar graph that does not have such a mixed layout. In addition, we study mixed layouts of graph subdivisions, and show that every planar graph has a mixed subdivision with one division vertex per edge
SERGEY YURIEVICH PREOBRAZHENSKY, SCHOLAR AND AUTHOR OF VERSES
No full textThe article is written in memoria of Sergey Yurievich Preobrahzhensky, linguist and poet. It tackles upon the scientific interests of the scholar, deals with his principal concepts in prosody and other spheres of poetics. Besides, It also contains a brief characteristics and examples of his own poetic work
Sergey Witte and his Foreign Investment Policy in the studies by English-speaking scholars
Full text link. The article discusses the development of the interest of English-speaking historians in the foreign investment policy of Sergey Witte. The paper also examines the role of the Secret Memorandum of Sergey Wittein the understanding of the foreign investment in the Russian economy. The author shows that Russian and English-speaking historians, despite the political upheavals of the 20th century, were engaged in a scholarly conversation in their discussion of the subject
The Price of Upwardness
Full text linkNot every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyond planarity by considering upward k-planar drawings of DAGs in which the edges are monotonically increasing in a common direction and every edge is crossed at most k times for some integer k≥1. We show that the number of crossings per edge in a monotone drawing is in general unbounded for the class of bipartite outerplanar, cubic, or bounded pathwidth DAGs. However, it is at most two for outerpaths and it is at most quadratic in the bandwidth in general. From the computational point of view, we prove that testing upward-k-planarity is NP-complete already for k=1 and even for restricted instances for which upward planarity testing is polynomial. On the positive side, we can decide in linear time whether a single-source DAG admits an upward 1-planar drawing in which all vertices are incident to the outer face
An Overview of Economics
No full textI assume that your objective of ’Economics 101’ is to try to understand how the economy works instead of going through an economic curriculum. If so you are guaranteed to have fun. I personally undertook a similar journey ten years back. I would say that it is better to understand the principles of economics and then try to understand the economy/economic situation of any given country. My recommendations (for BSc students and everyone who is interested in economics101) are based on my own readings: Sloman’s ”Essentials of economics;” Gwartney et al. ”Economics: Private Public Choice;” Jesus Huerta de Soto’s ”The Austrian School: Market Order and Entrepreneurial Creativity;” Rodrik’s ”Economics Rules;” Foley’s ”Adam’s fallacy: a guide to economic theology;” De Soto’s ”The mystery of capital: Why capitalism triumphs in the West and fails everywhere else;” Harford’s ”The Undercover Economist;” Levitt and Dubner’s ”Freakonomics.”This Paper should not be reported as representing the views of Central Bank of Armenia. The views in this paper are those of the author and should not be interpreted as those of Central Bank of Armenia
- …
