Fix a positive integer n and consider the bipartite graph whose vertices are the 3-element subsets and the 2-element subsets of [ n ] = { 1 , 2 , … , n } , and there is an edge between A and B if A ⊂ B . We prove that the domination number of this graph is n 2 − ⌊ ( n + 1 ) 2 8 ⌋ , we characterize the dominating sets of minimum size, and we observe that the minimum size dominating set can be chosen as an independent set. This is an exact version of an asymptotic result by Balogh, Katona, Linz and Tuza (2021). For the corresponding bipartite graph between the ( k + 1 ) -element subsets and the k -element subsets of [ n ] ( k ⩾ 3 ), we provide a new construction for small independent dominating sets. This improves on a construction by Gerbner, Kezegh, Lemons, Palmer, Pálvölgyi and Patkós (2012), who studied these independent dominating sets under the name saturating flat antichains.

A subset $S$ of initially infected vertices of a graph $G$ is called zero forcing if we can infect the entire graph by iteratively applying the following process. At each step, any infected vertex which has a unique uninfected neighbor, infects this neighbor. The zero forcing number of $G$ is the minimum cardinality of a zero forcing set in $G$. We study the zero forcing number of various classes of graphs, including graphs of large girth, $H$-free graphs for a fixed bipartite graph $H$, and random and pseudorandom graphs.

Sequential allocation is a simple and attractive mechanism for the allocation of indivisible goods used in a number of real world settings. In sequential allocation, agents pick items according to a policy, the order in which agents take turns. Sequential allocation will return an allocation which is Pareto efficient – no agent can do better without others doing worse. However, sequential allocation may not return the outcome that optimizes the social welfare. We consider therefore the relationship between the welfare and the efficiency of the allocations returned by sequential allocation mechanisms. We then study some simple computational questions about what welfare is possible or necessary depending on the choice of policy. Over half the problems we study turn out to be tractable, and we give polynomial time algorithms to compute them. We also consider a novel control problem in which the Chair chooses a policy to improve social welfare. Again, many of the control problems we study turn out to be tractable, and our results give polynomial time algorithms. In this case, tractability is a good thing so that the Chair can improve the social welfare of the allocation.

Abstract We study the problem of scheduling maintenance on arcs of a capacitated network to maximize the total flow from a source node to a sink node over a set of time periods. Maintenance on an arc shuts down the arc for the duration of the period in which its maintenance is scheduled, making its capacity zero for that period. A set of arcs is designated to have maintenance during the planning period, which will require each to be shut down for exactly one time period. In general this problem is known to be NP‐hard. Here we identify a number of characteristics that are relevant for the complexity of instance classes. In particular, we discuss instances with restrictions on the set of arcs that have maintenance to be scheduled; series‐parallel networks; capacities that are balanced, in the sense that the total capacity of arcs entering a (nonterminal) node equals the total capacity of arcs leaving the node; and identical capacities on all arcs. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(2), 196–202 2014

We study a simple sequential allocation mechanism for allocating indivisible goods between agents in which agents take turns to pick items.We focus on agents behaving strategically. We view the allocation procedure as a finite repeated game with perfect information. We show that with just two agents, we can compute the unique subgame perfect Nash equilibrium in linear time. With more agents, computing the subgame perfect Nash equilibria is more difficult. There can be an exponential number of equilibria and computing even one of them is PSPACE-hard. We identify a special case, when agents value many of the items identically, where we can efficiently compute the subgame perfect Nash equilibria. We also consider the effect of externalities and modifications to the mechanism that make it strategy proof.

Shape matrix decomposition is a subproblem in radiation therapy planning. A given fluence matrix A has to be written as a sum of shape matrices corresponding to homogeneous fields that can be shaped by a multileaf collimator. We solve the problem of finding an approximation B of A satisfying prescribed upper and lower bounds for each entry. The approximation B is determined such that the corresponding fluence can be realized with a prescribed delivery time using a multileaf collimator with an interleaf collision constraint, and under this condition the distance between A and B is minimized. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(2), 135–140 2011