205878836
A generalization of fan's condition and forbidden subgraph conditions for hamiltonicity
Abstract Let G be a 2-connected graph with n vertices and H be an induced subgraph of G. Denote V0 ≔ {v ϵ V(G): d(v) ⩾ n/2}. If there exists a pair of vertices x and y at distance 2 in H such that {x, y} ⊆ V(H)βV0, then H is called degree light. Let F be the unique graph with degree sequence (1, 1, 1, 3, 3, 3). In this paper, we prove that if G contains no degree light K1, 3 and every degree light F of G contains no induced P4 of G − V0, then G is hamiltonian.
29782824
Hamilton connectivity of line graphs and claw-free graphs
14260384
Perfect Circular Arc Coloring
The circular arc coloring problem is to find a minimum coloring of a set of arcs of a circle so that no two overlapping arcs share a color. This NP-hard problem arises in a rich variety of applications and has been studied extensively. In this paper we present an O(n2m) combinatorial algorithm for optimally coloring any set of arcs that corresponds to a perfect graph, and propose a new approach to the general circular arc coloring problem.
38894685
A Strongly Polynomial Algorithm for the Inverse Shortest Arborescence Problem
Abstract In this paper an inverse problem of the weighted shortest arborescence problem is discussed. That is, given a directed graph G and a set of nonnegative costs on its arcs, we need to modify those costs as little as possible to ensure that T, a given v1 -arborescence of G, is the shortest one. It is found that only the cost of T needs modifying. An O(n3) combinatorial algorithm is then proposed. This algorithm also gives an optimal solution to the inverse weighted shortest path problem.
14881107
Maximum Marking Problems with Accumulative Weight Functions
We present a new derivation of efficient algorithms for a class of optimization problems called maximum marking problems. We extend the class of weight functions used in the specification to allow for weight functions with accumulation, which is particularly useful when the weight of each element depends on adjacent elements. This extension of weight functions enables us to treat more interesting optimization problems such as a variant of the maximum segment sum problem and the fair bonus distribution problem. The complexity of the derived algorithm is linear with respect to the size of the input data.
7785528
A programmable editor for developing structured documents based on bidirectional transformations
This paper presents a novel editor supporting interactive refinement in the development of structured documents. The user performs a sequence of editing operations on the document view, and the editor automatically derives an efficient and reliable document source and a transformation that produces the document view. The editor is unique in its programmability, in the sense that the transformation can be obtained through editing operations. The main tricks behind are the utilization of the view-updating technique developed in the database community, and a new bidirectional transformation language that cannot only describe the relationship between the document source and its view, but also data dependency in the view.
12853199
Parallelization with Tree Skeletons
Trees are useful data structures, but to design efficient parallel programs over trees is known to be more difficult than to do over lists. Although several important tree skeletons have been proposed to simplify parallel programming on trees, few studies have been reported on how to systematically use them in solving practical problems; it is neither clear how to make a good combination of skeletons to solve a given problem, nor obvious even how to find suitable operators used in a single skeleton. In this paper, we report our first attempt to resolve these problems, proposing two important transformations, the tree diffusion transformation and the tree context preservation transformation. The tree diffusion transformation allows one to use familiar recursive definitions to develop his parallel programs, while the tree context preservation transformation shows how to derive associative operators that are required when using tree skeletons. We illustrate our approach by deriving an efficient parallel program for solving a nontrivial problem called the party planning problem, the tree version of the famous maximum-weight-sum problem.
11184766
Swapping Arguments and Results of Recursive Functions
Many useful calculation rules, such as fusion and tupling, rely on well-structured functions, especially in terms of inputs and outputs. For instance, fusion requires that well-produced outputs should be connected to well-consumed inputs, so that unnecessary intermediate data structures can be eliminated. These calculation rules generally fail to work unless functions are well-structured. In this paper, we propose a new calculation rule called IO swapping. IO swapping exchanges call-time computations (occurring in the arguments) and return-time computations (occurring in the results) of a function, while guaranteeing that the original and resulting function compute the same value. IO swapping enables us to rearrange inputs and outputs so that the existing calculation rules can be applied. We present new systematic derivations of efficient programs for detecting palindromes, and a method of higher-order removal that can be applied to defunctionalize function arguments, as two concrete applications.
5453797
List Homomorphism with Accumulation
This paper introduces accumulation into list homomorphisms for systematic development of both efficient and correct parallel programs. New parallelizable recursive pattern called H-homomorphism is given, and transformations from sequential patterns in the H-form and Hform into (H-)homomorphism are shown. We illustrate the power of our formalization by developing a novel and general parallel program for a class of interesting and challenging problems, known as maximum marking problems.