Results 141 to 150 of about 3,161 (171)
Optimal Local Certification on Graphs of Bounded Pathwidth [PDF]
ACM SIGACT-SIGOPS Symposium on Principles of Distributed ComputingWe present proof labeling schemes for graphs with bounded path-width that can decide any graph property expressible in monadic second-order (MSO2) logic using O(log n)-bit vertex labels.
Dan Alden Baterisna, Yi-Jun Chang
semanticscholar +2 more sources
On the Complexity of Telephone Broadcasting: From Cacti to Bounded Pathwidth Graphs [PDF]
International Colloquium on Automata, Languages and ProgrammingIn the Telephone Broadcasting problem, the goal is to disseminate a message from a given source vertex of an input graph to all other vertices in the minimum number of rounds, where at each round, an informed vertex can send the message to at most one of
Aida Aminian +3 more
semanticscholar +2 more sources
Randomly Coloring Graphs of Logarithmically Bounded Pathwidth
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2018 Shai Vardi
semanticscholar +3 more sources
Some of the next articles are maybe not open access.
Related searches:
Related searches:
2-Layer k-Planar Graphs: Density, Crossing Lemma, Relationships, and Pathwidth
International Symposium Graph Drawing and Network Visualization, 2020The $2$-layer drawing model is a well-established paradigm to visualize bipartite graphs where vertices of the two parts lie on two horizontal lines and edges lie between these lines.
Patrizio Angelini +3 more
semanticscholar +1 more source
PATHWIDTH AND LAYERED DRAWINGS OF TREES
International Journal of Computational Geometry & Applications, 2004An h-layer drawing of a graph G is a planar drawing of G in which each vertex is placed on one of h parallel lines and each edge is drawn as a straight line between its end-vertices. In such a drawing, we say that an edge is proper if its endpoints lie on adjacent layers, flat if they lie on the same layer and long otherwise.
openaire +3 more sources
Directed Pathwidth and Palletizers
2015In delivery industry, bins have to be stacked-up from conveyor belts onto pallets. Given k sequences of labeled bins and a positive integer p. The goal is to stack-up the bins by iteratively removing the first bin of one of the k sequences and put it onto a pallet located at one of p stack-up places.
Egon Wanke +2 more
openaire +2 more sources
Approximating the pathwidth of outerplanar graphs
Information Processing Letters, 1998Pathwidth is a well-known NP-complete graph metric. We present a technique to approximate the pathwidth of outerplanar graphs. Although a polynomial-time algorithm is already known to determine the pathwidth of outerplanar graphs, this algorithm is not practical.
Rajeev Govindan +2 more
openaire +2 more sources
Online Problems, Pathwidth, and Persistence [PDF]
, 2004 We explore the effects of using graph width metrics as restrictions on the input to online problems. It seems natural to suppose that, for graphs having some form of bounded width, good online algorithms may exist for a number of natural problems. In the work presented we concentrate on online graph coloring problems, where we restrict the allowed ...
Catherine McCartin, Rodney G. Downey
openaire +1 more source
Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
arXiv.orgIn the \textsc{Geodetic Set} problem, the input consists of a graph $G$ and a positive integer $k$. The goal is to determine whether there exists a subset $S$ of vertices of size $k$ such that every vertex in the graph is included in a shortest path ...
P. Tale
semanticscholar +1 more source
Pathwidth of 2-Layer k-Planar Graphs
arXiv.orgA bipartite graph $G = (X \cup Y, E)$ is a 2-layer $k$-planar graph if it admits a drawing on the plane such that the vertices in $X$ and $Y$ are placed on two parallel lines respectively, edges are drawn as straight-line segments, and every edge ...
Yuto Okada
semanticscholar +1 more source