43460576
Partitioning graphs of supply and demand
Assume that each vertex of a graph G is either a supply vertex or a demand vertex and is assigned a positive integer, called a supply or a demand. Each demand vertex can receive "power" from at most one supply vertex. One thus wishes to partition G into connected components by deleting edges from G so that each component C has exactly one supply vertex whose supply is no less than the sum of demands of all demand vertices in C. If G has no such partition, one wishes to partition G into connected components so that each component C either has no supply vertex or has exactly one supply vertex whose supply is no less than the sum of demands in C, and wishes to maximize the sum of demands in all components with supply vertices. We deal with such a maximization problem, which is NP-hard even for trees and strong NP-hard for general graphs. In this paper, we give a pseudo-polynomial-time algorithm to solve the problem for series-parallel graphs. The algorithm can be easily extended for partial k-trees, that is, graphs with bounded tree-width.
2226240
Partitioning Trees of Supply and Demand
Assume that a tree T has a number ns of "supply vertices" and all the other vertices are "demand vertices." Each supply vertex is assigned a positive number called a supply, while each demand vertex is assigned a positive number called a demand. One wish to partition T into exactly ns subtrees by deleting edges from T so that each subtree contains exactly one supply vertex whose supply is no less than the sum of demands of all demand vertices in the subtree. The "partition problem" is a decision problem to ask whether T has such a partition. The "maximum partition problem" is an optimization version of the partition problem. In this paper, we give three algorithms for the problems. First is a linear-time algorithm for the partition problem. Second is a pseudo-polynomial-time algorithm for the maximum partition problem. Third is a fully polynomial-time approximation scheme (FPTAS) for the maximum partition problem.
13514702
Partitioning a Multi-weighted Graph to Connected Subgraphs of Almost Uniform Size
Assume that each vertex of a graph G is assigned a constant number q of nonnegative integer weights, and that q pairs of nonnegative integers li and ui, 1 ≤i ≤q, are given. One wishes to partition G into connected components by deleting edges from G so that the total i-th weights of all vertices in each component is at least li and at most ui for each index i, 1 ≤i ≤q. The problem of finding such a “uniform” partition is NP-hard for series-parallel graphs, and is strongly NP-hard for general graphs even for q = 1. In this paper we show that the problem and many variants can be solved in pseudo-polynomial time for series-parallel graphs. Our algorithms for series-parallel graphs can be extended for partial k-trees, that is, graphs with bounded tree-width.
40835687
Partitioning trees of supply and demand
Assume that a tree T has a number ns of "supply vertices" and all the other vertices are "demand vertices." Each supply vertex is assigned a positive number called a supply, while each demand vertex is assigned a positive number called a demand. One wishes to partition T into exactly ns subtrees by deleting edges from T so that each subtree contains exactly one supply vertex whose supply is no less than the sum of demands of all demand vertices in the subtree. The "partition problem" is a decision problem to ask whether T has such a partition. The "maximum partition problem" is an optimization version of the partition problem. In this paper, we give three algorithms for the problems. The first is a linear-time algorithm for the partition problem. The second is a pseudo-polynomial-time algorithm for the maximum partition problem. The third is a fully polynomial-time approximation scheme (FPTAS) for the maximum partition problem.
32325022
Algorithms for Finding Distance-Edge-Colorings of Graphs
For a bounded integer l, we wish to color all edges of a graph G so that any two edges within distance l have different colors. Such a coloring is called a distance-edge-coloring or an l-edge-coloring of G. The distance-edge-coloring problem is to compute the minimum number of colors required for a distance-edge-coloring of a given graph G. A partial k-tree is a graph with tree-width bounded by a fixed constant k. We first present a polynomial-time exact algorithm to solve the problem for partial k-trees, and then give a polynomial-time 2-approximation algorithm for planar graphs.
10045838
Algorithms for finding distance-edge-colorings of graphs
For a bounded integer @?, we wish to color all edges of a graph G so that any two edges within distance @? have different colors. Such a coloring is called a distance-edge-coloring or an @?-edge-coloring of G. The distance-edge-coloring problem is to compute the minimum number of colors required for a distance-edge-coloring of a given graph G. A partial k-tree is a graph with tree-width bounded by a fixed constant k. We first present a polynomial-time exact algorithm to solve the problem for partial k-trees, and then give a polynomial-time 2-approximation algorithm for planar graphs.
39083447
A new distributed approach to solve meeting scheduling problems
Meeting Scheduling (MS) is an important real world-problem that is defined by the process of scheduling meetings while taking into account several constraints related to the availability and preferences of the users. The main contribution of this paper is to propose a new approach based on the DRAC model (distributed reinforcement of arc consistency) to solve the MS problem. A simplified version of this approach was implemented and compared with an approach of the state of the art. The experimental results show that our approach is scalable.
204985889
Regular graphs with excess one
Abstract It is shown that there exists no regular graph with excess e =1 and girth 2 r +1⩾5.
21650131
On a web browsing support system with 3d visualization
Existing commercial Web browsers provide various utilities and functions, e.g., Web bookmarks and a browsing history list. Since the bookmark and history functions only the title and URL of the Web page, users who cannot remember the contents of each Web page have difficulty retracing their steps. In this paper, we propose a bookmark system based on a 3D interface. Additionally, our system offers three main functions a 3D browsing history function, a marker function, and a look-ahead loading function. These functions enable users to browse Web pages more effectively.
40274616
On the spectra of certain distance-regular graphs
Let r be an undirected graph whose vertex-set V(F) is the set (ZJ~ , u2 ,..., v,>. The adjacency matrix of I’ is the n x n matrix A = A(r), over the complex number field, whose entries aij are given by a,j = 1 if vi and vi are adjacent, = 0 otherwise. DEFINITION 1. The spectrum of r is the set of distinct eigenvalues 4l , 4 ,**-> Od of A(F), together with their multiplicities, written m(&), m(4),..., m(0,). Since r is undirected, A is symmetric, and so the Bi are all real numbers. We arrange the Bi in increasing order, namely, 0, < O1 < *.. < e dMany studies have been done on the spectra of graphs by many mathematicians. Some of them may be found, for instance, in Biggs [2].
8383423
A Support Method for Qualitative Simulation-Based Learning System
In this paper, we mainly present a support method of our proposed e-learning system. We employ qualitative simulations because this lets the learners understand the conceptual principles in economic dynamics. First, we define some qualitative values employed on simulation graph model that consists of nodes and arcs. Then, we show the support method using our learning system based on qualitative simulation.