We study the problem of computing the vitality of edges and vertices with respect to the st$$ st $$‐max flow in undirected planar graphs, where the vitality of an edge/vertex is the st$$ st $$‐max ...flow decrease when the edge/vertex is removed from the graph. This allows us to establish the vulnerability of the graph with respect to the st$$ st $$‐max flow. We give efficient algorithms to compute an additive guaranteed approximation of the vitality of edges and vertices in planar undirected graphs. We show that in the general case high vitality values are well approximated in time close to the time currently required to compute st$$ st $$‐max flow O(nloglogn)$$ O\left(n\mathrm{loglog}n\right) $$. We also give improved, and sometimes optimal, results in the case of integer capacities. All our algorithms work in O(n)$$ O(n) $$ space.
This paper is concerned with a general class of distributed constrained optimization problems over a multiagent network, where the global objective function is represented by the sum of all local ...objective functions. Each agent in the network only knows its own local objective function, and is restricted to a global nonempty closed convex set. We discuss the scenario where the communication of the whole multiagent network is expressed as a sequence of time-varying general unbalanced directed graphs. The directed graphs are required to be uniformly jointly strongly connected and the weight matrices are only row-stochastic. To collaboratively deal with the optimization problems, existing distributed methods mostly require the communication graph to be fixed or balanced, which is impractical and hardly inevitable. In contrast, we propose a new distributed projection subgradient algorithm which is applicable to the time-varying general unbalanced directed graphs and does not need each agent to know its in-neighbors' out-degree. When the objective functions are convex and Lipschitz continuous, it is proved that the proposed algorithm exactly converges to the optimal solution. Simulation results on a numerical experiment are shown to substantiate feasibility of the proposed algorithm and correctness of the theoretical findings.
We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an
n
-vertex planar graph
G
is assigned a (1 + o(1)) log
2
n
-bit label and the labels of two vertices
u
...and
v
are sufficient to determine if
uv
is an edge of
G
. This is optimal up to the lower order term and is the first such asymptotically optimal result. An alternative, but equivalent, interpretation of this result is that, for every positive integer
n
, there exists a graph
U
n
with
n
1+o(1)
vertices such that every
n
-vertex planar graph is an induced subgraph of
U
n
. These results generalize to a number of other graph classes, including bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and
k
-planar graphs.
Numerous applications in scheduling, such as resource allocation or steel manufacturing, can be modeled using the NP-hard
Independent Set
problem (given an undirected graph and an integer
k
, find a ...set of at least
k
pairwise non-adjacent vertices). Here, one encounters special graph classes like 2-union graphs (edge-wise unions of two interval graphs) and strip graphs (edge-wise unions of an interval graph and a cluster graph), on which
Independent Set
remains
NP
-hard but admits constant ratio approximations in polynomial time. We study the parameterized complexity of
Independent Set
on 2-union graphs and on subclasses like strip graphs. Our investigations significantly benefit from a new structural “compactness” parameter of interval graphs and novel problem formulations using vertex-colored interval graphs. Our main contributions are as follows:
We show a complexity dichotomy: restricted to graph classes closed under induced subgraphs and disjoint unions,
Independent Set
is polynomial-time solvable if both input interval graphs are cluster graphs, and is
NP
-hard otherwise.
We chart the possibilities and limits of effective polynomial-time preprocessing (also known as kernelization).
We extend Halldórsson and Karlsson (
2006
)’s fixed-parameter algorithm for
Independent Set
on strip graphs parameterized by the structural parameter “maximum number of live jobs” to show that the problem (also known as
Job Interval Selection
) is fixed-parameter tractable with respect to the parameter
k
and generalize their algorithm from strip graphs to 2-union graphs. Preliminary experiments with random data indicate that
Job Interval Selection
with up to 15 jobs and
5
·
10
5
intervals can be solved optimally in less than 5 min.
A perfect Kr‐tiling in a graph G is a collection of vertex‐disjoint copies of Kr that together cover all the vertices in G. In this paper we consider perfect Kr‐tilings in the setting of randomly ...perturbed graphs; a model introduced by Bohman, Frieze, and Martin 7 where one starts with a dense graph and then adds m random edges to it. Specifically, given any fixed 0<α<1−1/r we determine how many random edges one must add to an n‐vertex graph G of minimum degree δ(G)≥αn to ensure that, asymptotically almost surely, the resulting graph contains a perfect Kr‐tiling. As one increases α we demonstrate that the number of random edges required “jumps” at regular intervals, and within these intervals our result is best‐possible. This work therefore closes the gap between the seminal work of Johansson, Kahn and Vu 25 (which resolves the purely random case, that is, α=0) and that of Hajnal and Szemerédi 18 (which demonstrates that for α≥1−1/r the initial graph already houses the desired perfect Kr‐tiling).
In a series of papers, of which this is the first, we study sufficient conditions for Hamiltonicity in terms of forbidden induced subgraphs and extend such results to locally finite infinite graphs. ...For this we use topological circles within the Freudenthal compactification of a locally finite graph as infinite cycles. In this paper we focus on conditions involving claws, nets and bulls as induced subgraphs. We extend Hamiltonicity results for finite claw‐free and net‐free graphs by Shepherd to locally finite graphs. Moreover, we generalise a classification of finite claw‐free and net‐free graphs by Shepherd to locally finite ones. Finally, we extend to locally finite graphs a Hamiltonicity result by Ryjáček involving a relaxed condition of being bull‐free.
The pineapple graph Kpq is obtained by appending q pendant edges to a vertex of a complete graph Kp (p≥3,q≥1). We prove that among connected graphs, the pineapple graph is determined by its adjacency ...spectrum. Moreover, we determine all disconnected graphs which are cospectral with a pineapple graph. Thus we find for which values of p and q the pineapple graph Kpq is determined by its adjacency spectrum. The main tool is a recent classification of all graphs with all but three eigenvalues equal to 0 or −1 by the third author.
PDF
