Separators in Graphs with Negative and Multiple Vertex Weights

A separator theorem for a class of graphs asserts that every graph in the class can be divided approximately in half by removing a set of vertices of specified size. Nontrivial separator theorems hold for several classes of graphs, including graphs of bounded genus and chordal graphs. We show that any separator theorem implies various weighted separator theorems. In particular, we show that if the vertices of the graph have real-valued weights, which may be positive or negative, then the graph can be divided exactly in half according to weight. If k unrelated sets of weights are given, the graph can be divided simultaneously by all k sets of weights. These results considerably strengthen earlier results of Gilbert, Lipton, and Tarjan: (1) for k=1 with the weights restricted to being nonnegative, and (2) for k>1 , nonnegative weights, and simultaneous division within a factor of (1+ε ) of exactly in half. Received November 21, 1995; revised October 30, 1997.     

Parallel Algorithms for Series Parallel Graphs and Graphs with Treewidth Two 1

In this paper a parallel algorithm is given that, given a graph G=(V,E) , decides whether G is a series parallel graph, and, if so, builds a decomposition tree for G of series and parallel composition rules. The algorithm uses O(log \kern -1pt |E|log ^\ast \kern -1pt |E|) time and O(|E|) operations on an EREW PRAM, and O(log \kern -1pt |E|) time and O(|E|) operations on a CRCW PRAM. The results hold for undirected as well as for directed graphs. Algorithms with the same resource bounds are described for the recognition of graphs of treewidth two, and for constructing tree decompositions of treewidth two. Hence efficient parallel algorithms can be found for a large number of graph problems on series parallel graphs and graphs with treewidth two. These include many well-known problems like all problems that can be stated in monadic second-order logic. Received July 15, 1997; revised January 29, 1999, and June 23, 1999.     

Fixed Parameter Algorithms for DOMINATING SET and Related Problems on Planar Graphs

Abstract. We present an algorithm that constructively produces a solution to the k -DOMINATING SET problem for planar graphs in time O(c^ \sqrt k n) , where c=4^ 6\sqrt 34 . To obtain this result, we show that the treewidth of a planar graph with domination number γ (G) is O(\sqrt \rule 0pt 4pt \smash γ (G) ) , and that such a tree decomposition can be found in O(\sqrt \rule 0pt 4pt \smash γ (G) n) time. The same technique can be used to show that the k -FACE COVER problem (find a size k set of faces that cover all vertices of a given plane graph) can be solved in O(c ₁ ^ \sqrt k n) time, where c ₁ =3^ 36\sqrt 34 and k is the size of the face cover set. Similar results can be obtained in the planar case for some variants of k -DOMINATING SET, e.g., k -INDEPENDENT DOMINATING SET and k -WEIGHTED DOMINATING SET.     

Improved Algorithms and Complexity Results for Power Domination in Graphs

The NP-complete Power Dominating Set problem is an “electric power networks variant” of the classical domination problem in graphs: Given an undirected graph G=(V,E), find a minimum-size set P?V such that all vertices in V are “observed” by the vertices in P. Herein, a vertex observes itself and all its neighbors, and if an observed vertex has all but one of its neighbors observed, then the remaining neighbor becomes observed as well. We show that Power Dominating Set can be solved by “bounded-treewidth dynamic programs.” For treewidth being upper-bounded by a constant, we achieve a linear-time algorithm. In particular, we present a simplified linear-time algorithm for Power Dominating Set in trees. Moreover, we simplify and extend several NP-completeness results, particularly showing that Power Dominating Set remains NP-complete for planar graphs, for circle graphs, and for split graphs. Specifically, our improved reductions imply that Power Dominating Set parameterized by |P| is W[2]-hard and it cannot be better approximated than Dominating Set.     

Partitioning a Square into Rectangles: NP-Completeness and Approximation Algorithms

   Abstract. In this paper we deal with two geometric problems arising from heterogeneous parallel computing: how to partition the unit square into p rectangles of given area s ₁ , s ₂ , . . . ,s _p (such that Σ _i=1 ^p s _i = 1 ), so as to minimize either (i) the sum of the p perimeters of the rectangles or (ii) the largest perimeter of the p rectangles? For both problems, we prove NP-completeness and we introduce a 7/4 -approximation algorithm for (i) and a

Computing the Treewidth and the Minimum Fill-In with the Modular Decomposition

Abstract. Using the notion of modular decomposition we extend the class of graphs on which both the treewidth and the minimum fill-in can be solved in polynomial time. We show that if C is a class of graphs that are modularly decomposable into graphs that have a polynomial number of minimal separators, or graphs formed by adding a matching between two cliques, then both the treewidth and the minimum fill-in on C can be solved in polynomial time. For the graphs that are modular decomposable into cycles we give algorithms that use respectively O(n) and O(n ³ ) time for treewidth and minimum fill-in.     

Planar Minimization Diagrams via Subdivision with Applications to Anisotropic Voronoi Diagrams

Let X = {f₁, …, f_n} be a set of scalar functions of the form f_i : ?² → ? which satisfy some natural properties. We describe a subdivision algorithm for computing a clustered ε‐isotopic approximation of the minimization diagram of X. By exploiting soft predicates and clustering of Voronoi vertices, our algorithm is the first that can handle arbitrary degeneracies in X, and allow scalar functions which are piecewise smooth, and not necessarily semi‐algebraic. We apply these ideas to the computation of anisotropic Voronoi diagram of polygonal sets; this is a natural generalization of anisotropic Voronoi diagrams of point sites, which extends multiplicatively weighted Voronoi diagrams. We implement a prototype of our anisotropic algorithm and provide experimental results.     

Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover

We present a new method of solving graph problems related to Vertex Cover by enumerating and expanding appropriate sets of nodes. As an application, we obtain dramatically improved runtime bounds for two variants of the Vertex Cover problem. In the case of Connected Vertex Cover, we take the upper bound from O ^*(6 ^k ) to O ^*(2.7606 ^k ) without large hidden factors. For Tree Cover, we show a complexity of O ^*(3.2361 ^k ), improving over the previous bound of O ^*((2k) ^k ). In the process, faster algorithms for solving subclasses of the Steiner tree problem on graphs are investigated. Supported by the DFG under grant RO 927/6-1 (TAPI).     

Quasi-Fully Dynamic Algorithms for Two-Connectivity and Cycle Equivalence

We introduce a new class of dynamic graph algorithms called quasi-fully dynamic algorithms , which are much more general than backtracking algorithms and are much simpler than fully dynamic algorithms. These algorithms are especially suitable for applications in which a certain core connected portion of the graph remains fixed, and fully dynamic updates occur on the remaining edges in the graph. We present very simple quasi-fully dynamic algorithms with O(log n) worst-case time per operation for 2-edge connectivity and O(log n) amortized time per operation for cycle equivalence. The former is deterministic while the latter is Monte-Carlo-type randomized. For 2-vertex connectivity, we give a deterministic quasi-fully dynamic algorithm with O(log ³ n) amortized time per operation. The quasi-fully dynamic algorithm we present for cycle equivalence (which has several applications in optimizing compilers) is of special interest since the algorithm is quite simple, and no special-purpose incremental or backtracking algorithm is known for this problem. Received October 26, 1998; revised October 1, 1999, and April 15, 2001.     

Computations with quasiseparable polynomials and matrices

In this paper, we survey several recent results that highlight an interplay between a relatively new class of quasiseparable matrices and univariate polynomials. Quasiseparable matrices generalize two classical matrix classes, Jacobi (tridiagonal) matrices and unitary Hessenberg matrices that are known to correspond to real orthogonal polynomials and Szegö polynomials, respectively. The latter two polynomial families arise in a wide variety of applications, and their short recurrence relations are the basis for a number of efficient algorithms. For historical reasons, algorithm development is more advanced for real orthogonal polynomials. Recent variations of these algorithms tend to be valid only for the Szegö polynomials; they are analogues and not generalizations of the original algorithms.     

Caching Documents with Variable Sizes and Fetching Costs: An LP-Based Approach

Abstract. We give an integer programming formulation of the paging problem with varying sizes and fetching costs. We use this formulation to provide an alternative proof that a variant of the algorithm greedy-dual-size previously considered in [4] and [5] is (k+1)/(k-h+1) competitive against the optimal strategy with cache size h≤ k . Our proof provides further insights to greedy-dual-size. We also indicate how the same integer programming formulation has been recently used [1], [2] to obtain approximation algorithms to the NP-complete ``offline' problem.     

Rendering Plasma Phenomena: Applications and Challenges

Plasmas are ubiquitous in the Universe. An understanding of plasma phenomena is therefore of importance in almost every area of astrophysics, from stellar atmospheres to star clusters. Plasmas also occur in daily life both in industrial processes and in consumer products. Recent groundbreaking data is making this the golden age of plasma science. Although direct observations and analysis of data provide important physical evidence for plasma phenomena, they do not necessarily explain the phenomena. Hence, recent discoveries in this area might not only arise out of observations, but also from visual simulations of the phenomena supported by advanced rendering technologies. This report describes the state of art of such simulations, and examines practical issues often overlooked in the literature. Educational and public outreach applications are also discussed. Although the emphasis is on the predictive rendering of plasma processes, the simulation guidelines and trade-offs addressed in this report can be extended to other types of natural phenomena. The report closes with a discussion of further avenues of research involving the visual simulation of plasma phenomena.     

Piecewise‐Planar 3D Reconstruction with Edge and Corner Regularization

This paper presents a method for the 3D reconstruction of a piecewise‐planar surface from range images, typically laser scans with millions of points. The reconstructed surface is a watertight polygonal mesh that conforms to observations at a given scale in the visible planar parts of the scene, and that is plausible in hidden parts. We formulate surface reconstruction as a discrete optimization problem based on detected and hypothesized planes. One of our major contributions, besides a treatment of data anisotropy and novel surface hypotheses, is a regularization of the reconstructed surface w.r.t. the length of edges and the number of corners. Compared to classical area‐based regularization, it better captures surface complexity and is therefore better suited for man‐made environments, such as buildings. To handle the underlying higher‐order potentials, that are problematic for MRF optimizers, we formulate minimization as a sparse mixed‐integer linear programming problem and obtain an approximate solution using a simple relaxation. Experiments show that it is fast and reaches near‐optimal solutions.     

Non Uniform Multiresolution Method for Optical Flow and Phase Portrait Models: Environmental Applications

In this paper we define a complete framework for processing large image sequences for a global monitoring of short range oceanographic and atmospheric processes. This framework is based on the use of a non quadratic regularization technique for optical flow computation that preserves flow discontinuities. We also show that using an appropriate tessellation of the image according to an estimate of the motion field can improve optical flow accuracy and yields more reliable flows. This method defines a non uniform multiresolution approach for coarse to fine grid generation. It allows to locally increase the resolution of the grid according to the studied problem. Each added node refines the grid in a region of interest and increases the numerical accuracy of the solution in this region. We make use of such a method for solving the optical flow equation with a non quadratic regularization scheme allowing the computation of optical flow field while preserving its discontinuities. The second part of the paper deals with the interpretation of the obtained displacement field. For this purpose a phase portrait model used along with a new formulation of the approximation of an oriented flow field allowing to consider arbitrary polynomial phase portrait models for characterizing salient flow features. This new framework is used for processing oceanographic and atmospheric image sequences and presents an alternative to complex physical modeling techniques.     

Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-Linear Objectives with Applications

We provide an improved FPTAS for multiobjective shortest paths—a fundamental (NP-hard) problem in multiobjective optimization—along with a new generic method for obtaining FPTAS to any multiobjective optimization problem with non-linear objectives. We show how these results can be used to obtain better approximate solutions to three related problems, multiobjective constrained [optimal] path and non-additive shortest path, that have important applications in QoS routing and in traffic optimization. We also show how to obtain a FPTAS to a natural generalization of the weighted multicommodity flow problem with elastic demands and values that models several realistic scenarios in transportation and communication networks. This work was partially supported by the Future and Emerging Technologies Unit of EC (IST priority—6th FP), under contracts No. IST-2002-001907 (integrated project DELIS) and No. FP6-021235-2 (project ARRIVAL), and the Action PYTHAGORAS of the Operational Programme for Educational & Vocational Training II, with matching funds from the European Social Fund and the Greek Ministry of Education.     

A workflow for handling heterogeneous 3D models with the TOUGH2 family of codes: Applications to numerical modeling of CO2 geological storage

This paper is addressed to the TOUGH2 user community. It presents a new tool for handling simulations run with the TOUGH2 code with specific application to CO₂ geological storage. This tool is composed of separate FORTRAN subroutines (or modules) that can be run independently, using input and output files in ASCII format for TOUGH2. These modules have been developed specifically for modeling of carbon dioxide geological storage and their use with TOUGH2 and the Equation of State module ECO2N, dedicated to CO₂-water-salt mixture systems, with TOUGHREACT, which is an adaptation of TOUGH2 with ECO2N and geochemical fluid-rock interactions, and with TOUGH2 and the EOS7C module dedicated to CO₂-CH₄ gas mixture is described. The objective is to save time for the pre-processing, execution and visualization of complex geometry for geological system representation. The workflow is rapid and user-friendly and future implementation to other TOUGH2 EOS modules for other contexts (e.g. nuclear waste disposal, geothermal production) is straightforward. Three examples are shown for validation: (i) leakage of CO₂ up through an abandoned well; (ii) 3D reactive transport modeling of CO₂ in a sandy aquifer formation in the Sleipner gas Field, (North Sea, Norway); and (iii) an estimation of enhanced gas recovery technology using CO₂ as the injected and stored gas to produce methane in the K12B Gas Field (North Sea, Denmark).     

Mechanical ventilation and thoracic artificial lung assistance during mechanical circulatory support with PUCA pump: In silico study

Patients assisted with left ventricular assist device (LVAD) may require prolonged mechanical ventilatory assistance secondary to postoperative respiratory failure. The goal of this work is the study of the interdependent effects LVAD like pulsatile catheter (PUCA) pump and mechanical ventilatory support or thoracic artificial lung (TAL), by the hemodynamic point of view, using a numerical simulator of the human cardiovascular system. In the simulator, different circulatory sections are described using lumped parameter models. Lumped parameter models have been designed to describe the hydrodynamic behavior of both PUCA pump and thoracic artificial lung. Ventricular behavior atrial and septum functions were reproduced using variable elastance model. Starting from simulated pathological conditions we studied the effects produced on some hemodynamic variables by simultaneous PUCA pump, thoracic artificial lung or mechanical ventilation assistance. Thoracic artificial lung was applied in parallel or in hybrid mode. The effects of mechanical ventilation have been simulated by changing mean intrathoracic pressure value from −4 mmHg to +5 mmHg. The hemodynamic variables observed during the simulations, in different assisted conditions, were: left and right ventricular end systolic (diastolic) volume, systolic/diastolic aortic pressure, mean pulmonary arterial pressure, left and right mean atrial pressure, mean systemic venous pressure and the total blood flow. Results show that the application of PUCA (without mechanical ventilatory assistance) increases the total blood flow, reduces the left ventricular end systolic volume and increases the diastolic aortic pressure. Parallel TAL assistance increases the right ventricular end diastolic (systolic) volume reduction both when PUCA is switched “ON” and both when PUCA is switched “OFF”. By switching “OFF” the PUCA pump, it seems that parallel thoracic artificial lung assistance produces a greater cardiac output (respect to hybrid TAL assistance).