Small maximal independent sets and faster exact graph coloring.
Small stretch spanners on dynamic graphs.
Some algorithms on the star operation applied to finite languages.
Some graphic uses of an even number of odd nodes
Vertex-degree parity in large implicit “exchange graphs” implies some EP theorems asserting the existence of a second object without evidently providing a polytime algorithm for finding a second object.
Some Heuristics in Automatic Theorem Proving
Some heuristics in automatic theorem proving.
Some Provably Hard Crossing Number Problems.
Spanning trees with leaves bounded by independence number.
Spectral Recognition of Graphs
Square-root rule of two-dimensional bandwidth problem
The bandwidth minimization problem is of significance in network communication and related areas. Let G be a graph of n vertices. The two-dimensional bandwidth B2(G) of G is the minimum value of the maximum distance between adjacent vertices when G is embedded into an n × n grid in the plane. As a discrete optimization problem, determining B2(G) is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This paper studies the “square-root...
Square-root rule of two-dimensional bandwidth problem∗
The bandwidth minimization problem is of significance in network communication and related areas. Let G be a graph of n vertices. The two-dimensional bandwidth B2(G) of G is the minimum value of the maximum distance between adjacent vertices when G is embedded into an n × n grid in the plane. As a discrete optimization problem, determining B2(G) is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This paper studies the “square-root...
Stacks, queues and tracks: layouts of graph subdivisions.
Straight-line drawings of binary trees with linear area and arbitrary aspect ratio.
Straight-line drawings on restricted integer grids in two and three dimensions.
Strict refinement for direct sums and graphs.
Structural Properties of Recursively Partitionable Graphs with Connectivity 2
A connected graph G is said to be arbitrarily partitionable (AP for short) if for every partition (n1, . . . , np) of |V (G)| there exists a partition (V1, . . . , Vp) of V (G) such that each Vi induces a connected subgraph of G on ni vertices. Some stronger versions of this property were introduced, namely the ones of being online arbitrarily partitionable and recursively arbitrarily partitionable (OL-AP and R-AP for short, respectively), in which the subgraphs induced by a partition of G must...
Studying graph - stability to apprehend relative hardness of constructive-non-constructive approximation
Sur le nombre de registres nécessaires à l'évaluation d'une expression arithmétique
Symmetry breaking in graphs.
Techniques for the refinement of orthogonal graph drawings.