205876923
Number of maximum matchings of bipartite graphs with positive surplus
A bipartite graph G=(A,B) is said to have positive surplus (as viewed from A) if the number of neighbors of X is bigger than the size of X for any non-empty subset X of A. In this paper, two lower bounds on the number of maximum matchings in bipartite graphs with positive surplus are obtained. The enumeration problems for maximum matchings in special bipartite graphs are solved. From this, the number of perfect matchings of some elementary bipartite graphs is given.
43698695
The fractional matching numbers of graphs
A fractional matching of a graph G is a function f that assigns to each edge a number in [0, 1] such that, for each vertex v, ∑ f(e) ≤ 1, where the sum is taken over all edges incident to v. The fractional matching number of G is the supremum of ∑e∈E(G)f(e) over all fractional matchings f. In this paper, we provide a new formula for calculating the fractional matching numbers of graphs using the Gallai–Edmonds Structure Theorem. Thus, we characterize graphs for which the fractional matching number equals the matching number and graphs for which the fractional matching number is the maximum possible (one-half the number of vertices). © 2002 Wiley Periodicals, Inc.
5645902
On designing incentive-compatible routing and forwarding protocols in wireless ad-hoc networks: an integrated approach using game theoretical and cryptographic techniques
In many applications, wireless ad-hoc networks are formed by devices belonging to independent users. Therefore, a challenging problem is how to provide incentives to stimulate cooperation. In this paper, we study ad-hoc games---the routing and packet forwarding games in wireless ad-hoc networks. Unlike previous work which focuses either on routing or on forwarding, this paper investigates both routing and forwarding. We first uncover an impossibility result---there does not exist a protocol such that following the protocol to always forward others' traffic is a dominant action. Then we define a novel solution concept called cooperation-optimal protocols. We present Corsac, a cooperation-optimal protocol consisting of a routing protocol and a forwarding protocol. The routing protocol of Corsac integrates VCG with a novel cryptographic technique to address the challenge in wireless ad-hoc networks that a link's cost (ie, its type) is determined by two nodes together. Corsac also applies efficient cryptographic techniques to design a forwarding protocol to enforce the routing decision, such that fulfilling the routing decision is the optimal action of each node in the sense that it brings the maximum utility to the node. Additionally, we extend our framework to a practical radio propagation model where a transmission is successful with a probability. We evaluate our protocols using simulations. Our evaluations demonstrate that our protocols provide incentives for nodes to forward packets.
2123278
Program optimization using indexed and recursive data structures
This paper describes a systematic method for optimizing recursive functions using both indexed and recursive data structures. The method is based on two critical ideas: first, determining a minimal input increment operation so as to compute a function on repeatedly incremented input; second, determining appropriate additional values to maintain in appropriate data structures, based on what values are needed in computation on an incremented input and how these values can be established and accessed. Once these two are determined, the method extends the original program to return the additional values, derives an incremental version of the extended program, and forms an optimized program that repeatedly calls the incremental program. The method can derive all dynamic programming algorithms found in standard algorithm textbooks. There are many previous methods for deriving efficient algorithms, but none is as simple, general, and systematic as ours.
34451404
The enumeration of near-perfect matchings of factor-critical graphs
Abstract A matching of a graph is a near-perfect matching if it covers all but one vertex. A connected graph G is said to be factor-critical if G − v has perfect matchings for every vertex v of G. In this paper, the enumeration problems for near-perfect matchings in special factor-critical graphs are solved. From this, the exact values of the number of perfect matchings in special bicritical graphs are obtained.
10742303
Stability and sensitivity for congestion control in wireless networks with time varying link capacities
While extensive efforts have been devoted to providing optimization based, distributed congestion control schemes for efficient bandwidth utilization and fair allocation in both wireline and wireless networks, a common assumption therein is fixed link capacities. This unfortunately will limit the application scope in multi-hop wireless networks where channels are ever changing. In this paper, we explicitly model link capacities to be time varying and investigate congestion control problems in multi-hop wireless networks. In particular we propose a primal-dual congestion control algorithm which is proved to be trajectory stable in the absence of feedback delay. Different from system stability around a single equilibrium point, trajectory stability Guarantees the system is stable around a time varying reference trajectory. Moreover, we obtain sufficient conditions for the scheme to be locally stable in the presence of delay. Our key technique is to model time variations of capacities as perturbations to a constant link. Furthermore, to study the robustness of the algorithm against capacity variations, we investigate the sensitivity of the control scheme and through simulations to study the tradeoff between stability and sensitivity.
36530209
Determination of the star valency of a graph
The star valency of a graph G is the minimum, over all star decompositions π, of the maximum number of elements in π incident with a vertex. The maximum average degree of G, denoted by dmax-ave(G), is the maximum average degree of all subgraphs of G. In this paper, we prove that the star valency of G is either ⌈dmax-ave(G)/2⌉ or ⌈dmax-ave(G)/2⌉ + 1, and provide a polynomial time algorithm for determining the star valency of a graph.