112 citations · 298 across the 40 of their papers we have counts for
13 papers · 1 filter
Minimum Coverage Instrumentation
Li Chen, Ellis Hoag, Kyungwoo Lee +2
Modern compilers leverage block coverage profile data to carry out downstream profile-guided optimizations to improve the runtime performance and the size of a binary. Given a cont…
On the Extended TSP Problem
Julián Mestre, Sergey Pupyrev, Seeun William Umboh
We initiate the theoretical study of Ext-TSP, a problem that originates in the area of profile-guided binary optimization. Given a graph with positive edge weights $w: E…
The Mixed Page Number of Graphs
Jawaherul Md. Alam, Michael A. Bekos, Martin Gronemann +2
A linear layout of a graph typically consists of a total vertex order, and a partition of the edges into sets of either non-crossing edges, called stacks, or non-nested edges, call…
Lazy Queue Layouts of Posets
Jawaherul Md. Alam, Michael A. Bekos, Martin Gronemann +2
We investigate the queue number of posets in terms of their width, that is, the maximum number of pairwise incomparable elements. A long-standing conjecture of Heath and Pemmaraju…
Four Pages Are Indeed Necessary for Planar Graphs
Michael A. Bekos, Michael Kaufmann, Fabian Klute +3
An embedding of a graph in a book consists of a linear order of its vertices along the spine of the book and of an assignment of its edges to the pages of the book, so that no two…
Multi-Dimensional Balanced Graph Partitioning via Projected Gradient Descent
Dmitrii Avdiukhin, Sergey Pupyrev, Grigory Yaroslavtsev
Motivated by performance optimization of large-scale graph processing systems that distribute the graph across multiple machines, we consider the balanced graph partitioning proble…
Queue Layouts of Planar 3-Trees
Jawaherul Md. Alam, Michael A. Bekos, Martin Gronemann +2
A queue layout of a graph G consists of a linear order of the vertices of G and a partition of the edges of G into queues, so that no two independent edges of the same queue are ne…
Social Hash Partitioner: A Scalable Distributed Hypergraph Partitioner
Igor Kabiljo, Brian Karrer, Mayank Pundir +4
We design and implement a distributed algorithm for balanced -way hypergraph partitioning that minimizes fanout, a fundamental hypergraph quantity also known as the communicatio…
Compressing Graphs and Indexes with Recursive Graph Bisection
Laxman Dhulipala, Igor Kabiljo, Brian Karrer +3
Graph reordering is a powerful technique to increase the locality of the representations of graphs, which can be helpful in several applications. We study how the technique can be…
Improved Approximation Algorithms for Box Contact Representations
Michael A. Bekos, Thomas C. van Dijk, Martin Fink +5
We study the following geometric representation problem: Given a graph whose vertices correspond to axis-aligned rectangles with fixed dimensions, arrange the rectangles without ov…
Metro-Line Crossing Minimization: Hardness, Approximations, and Tractable Cases
Martin Fink, Sergey Pupyrev
Crossing minimization is one of the central problems in graph drawing. Recently, there has been an increased interest in the problem of minimizing crossings between paths in drawin…
Happy Edges: Threshold-Coloring of Regular Lattices
Md. Jawaherul Alam, Stephen G. Kobourov, Sergey Pupyrev +1
We study a graph coloring problem motivated by a fun Sudoku-style puzzle. Given a bipartition of the edges of a graph into {\em near} and {\em far} sets and an integer threshold $t…
On Semantic Word Cloud Representation
Lukas Barth, Stephen Kobourov, Sergey Pupyrev +1
We study the problem of computing semantic-preserving word clouds in which semantically related words are close to each other. While several heuristic approaches have been describe…