Search Results

Advanced search parameters have been applied.
open access

Level-treewidth property, exact algorithms and approximation schemes

Description: Informally, a class of graphs Q is said to have the level-treewidth property (LT-property) if for every G {element_of} Q there is a layout (breadth first ordering) L{sub G} such that the subgraph induced by the vertices in k-consecutive levels in the layout have treewidth O(f (k)), for some function f. We show that several important and well known classes of graphs including planar and bounded genus graphs, (r, s)-civilized graphs, etc, satisfy the LT-property. Building on the recent work, we p… more
Date: June 1, 1997
Creator: Marathe, M. V.; Hunt, H. B. & Stearns, R. E.
Partner: UNT Libraries Government Documents Department
open access

Towards syntactic characterizations of approximation schemes via predicate and graph decompositions

Description: The authors present a simple extensible theoretical framework for devising polynomial time approximation schemes for problems represented using natural syntactic (algebraic) specifications endowed with natural graph theoretic restrictions on input instances. Direct application of the technique yields polynomial time approximation schemes for all the problems studied in [LT80, NC88, KM96, Ba83, DTS93, HM+94a, HM+94] as well as the first known approximation schemes for a number of additional comb… more
Date: December 1, 1998
Creator: Hunt, H. B., III; Stearns, R. E.; Jacob, R. & Marathe, M. V.
Partner: UNT Libraries Government Documents Department
open access

Generalized CNF satisfiability, local reductions and complexity of succinctly specified problems

Description: We, study the complexity and efficient approximability of various decision, counting and optimization problems when instances are specified using (1) the 1-dimensional finite periodic narrow specifications of Wanke, (2) the 2-way infinite 1-dimensional narrow periodic (sometimes called dynamic) specifications of Karp and Orlin et al., and (3) the hierarchical specification language of Lengauer et al. We outline how generalized CNF satisfiability problems and local reductions can be used to obta… more
Date: February 1, 1995
Creator: Marathe, M. V.; Hunt, H. B., III; Stearns, R. E. & Radhakrishnan, V.
Partner: UNT Libraries Government Documents Department
open access

Approximation algorithms for NEXTtime-hard periodically specified problems and domino problems

Description: We study the efficient approximability of two general class of problems: (1) optimization versions of the domino problems studies in [Ha85, Ha86, vEB83, SB84] and (2) graph and satisfiability problems when specified using various kinds of periodic specifications. Both easiness and hardness results are obtained. Our efficient approximation algorithms and schemes are based on extensions of the ideas. Two of properties of our results obtained here are: (1) For the first time, efficient approximati… more
Date: February 1, 1996
Creator: Marathe, M. V.; Hunt, H. B., III; Stearns, R. E. & Rosenkrantz, D. J.
Partner: UNT Libraries Government Documents Department
open access

Theory of periodically specified problems: Complexity and approximability

Description: We study the complexity and the efficient approximability of graph and satisfiability problems when specified using various kinds of periodic specifications studied. The general results obtained include the following: (1) We characterize the complexities of several basic generalized CNF satisfiability problems SAT(S) [Sc78], when instances are specified using various kinds of 1- and 2-dimensional periodic specifications. We outline how this characterization can be used to prove a number of new … more
Date: December 5, 1997
Creator: Marathe, M. V.; Hunt, H. B., III; Stearns, R. E. & Rosenkrantz, D. J.
Partner: UNT Libraries Government Documents Department
open access

COMPLEXITY&APPROXIMABILITY OF QUANTIFIED&STOCHASTIC CONSTRAINT SATISFACTION PROBLEMS

Description: Let D be an arbitrary (not necessarily finite) nonempty set, let C be a finite set of constant symbols denoting arbitrary elements of D, and let S and T be an arbitrary finite set of finite-arity relations on D. We denote the problem of determining the satisfiability of finite conjunctions of relations in S applied to variables (to variables and symbols in C) by SAT(S) (by SATc(S).) Here, we study simultaneously the complexity of decision, counting, maximization and approximate maximization pro… more
Date: January 1, 2001
Creator: Hunt, H. B. (Harry B.); Marathe, M. V. (Madhav V.) & Stearns, R. E. (Richard E.)
Partner: UNT Libraries Government Documents Department
open access

Periodically specified problems: An exponential complexity gap between exact and approximate solutions

Description: We study both the complexity and approximability of various graph and combinatorial problems specified using two dimensional narrow periodic specifications (see [CM93, HW92, KMW67, KO91, Or84b, Wa93]). The following two general kinds of results are presented. (1) We prove that a number of natural graph and combinatorial problems are NEXPTIME- or EXPSPACE-complete when instances are so specified; (2) In contrast, we prove that the optimization versions of several of these NEXPTIME-, EXPSPACE-com… more
Date: November 28, 1994
Creator: Hunt, H. B., III; Rosenkrantz, D. J.; Stearns, R. E.; Marathe, M. V. & Radhakrishnan, V.
Partner: UNT Libraries Government Documents Department
open access

Complexity and efficient approximability of two dimensional periodically specified problems

Description: The authors consider the two dimensional periodic specifications: a method to specify succinctly objects with highly regular repetitive structure. These specifications arise naturally when processing engineering designs including VLSI designs. These specifications can specify objects whose sizes are exponentially larger than the sizes of the specification themselves. Consequently solving a periodically specified problem by explicitly expanding the instance is prohibitively expensive in terms of… more
Date: September 1, 1996
Creator: Marathe, M. V.; Hunt, H. B., III & Stearns, R. E.
Partner: UNT Libraries Government Documents Department
open access

Periodically specified satisfiability problems with applications: An alternative to domino problems

Description: We characterize the complexities of several basic generalized CNF satisfiability problems SAT(S), when instances are specified using various kinds of 1- and 2-dimensional periodic specifications. We outline how this characterization can be used to prove a number of new hardness results for the complexity classes DSPACE(n), NSPACE(n), DEXPTIME, NEXPTIME, EXPSPACE etc. The hardness results presented significantly extend the known hardness results for periodically specified problems. Several advan… more
Date: December 31, 1995
Creator: Marathe, M. V.; Hunt, H. B., III; Rosenkrantz, D. J.; Stearns, R. E. & Radhakrishnann, V.
Partner: UNT Libraries Government Documents Department
open access

Complexity of hierarchically and 1-dimensional periodically specified problems

Description: We study the complexity of various combinatorial and satisfiability problems when instances are specified using one of the following specifications: (1) the 1-dimensional finite periodic narrow specifications of Wanke and Ford et al. (2) the 1-dimensional finite periodic narrow specifications with explicit boundary conditions of Gale (3) the 2-way infinite1-dimensional narrow periodic specifications of Orlin et al. and (4) the hierarchical specifications of Lengauer et al. we obtain three gener… more
Date: August 23, 1995
Creator: Marathe, M. V.; Hunt, H. B., III; Stearns, R. E. & Radhakrishnan, V.
Partner: UNT Libraries Government Documents Department
open access

Bicriteria Network Design Problems

Description: We study several bicriteria network design problems phrased as follows: given an indirected graph and two minimization objectives with a budget specified on one objective, find a subgraph satisfying certain connectivity requirements that minimizes the second objective subject to the budget on the first. First, we develop a formalism for bicriteria problems and their approximations. Secondly, we use a simple parametric search technique to provide bicriteria approximation algorithms for problems … more
Date: May 1, 1995
Creator: Marathe, M. V.; Ravi, R.; Sundaram, R.; Ravi, S. S.; Rosenkrantz, D. J. & Hunt, H. B., III
Partner: UNT Libraries Government Documents Department
open access

Predecessor and permutation existence problems for sequential dynamical systems

Description: A class of finite discrete dynamical systems, called Sequential Dynamical Systems (SDSs), was introduced in BMR99, BR991 as a formal model for analyzing simulation systems. An SDS S is a triple (G, F,n ),w here (i) G(V,E ) is an undirected graph with n nodes with each node having a state, (ii) F = (fi, fi, . . ., fn), with fi denoting a function associated with node ui E V and (iii) A is a permutation of (or total order on) the nodes in V, A configuration of an SDS is an n-vector ( b l, bz, . .… more
Date: January 1, 2002
Creator: Barrett, C. L. (Christopher L.); Hunt, H. B. (Harry B.); Marathe, M. V. (Madhav V.); Rosenkrantz, D. J. (Daniel J.) & Stearns, R. E. (Richard E.)
Partner: UNT Libraries Government Documents Department
open access

Complexity of analysis and verification problems for communicating automata and discrete dynamical systems.

Description: We identify several simple but powerful concepts, techniques, and results; and we use them to characterize the complexities of a number of basic problems II, that arise in the analysis and verification of the following models M of communicating automata and discrete dynamical systems: systems of communicating automata including both finite and infinite cellular automata, transition systems, discrete dynamical systems, and succinctly-specified finite automata. These concepts, techniques, and res… more
Date: January 1, 2001
Creator: Hunt, H. B. (Harry B.); Rosenkrantz, D. J. (Daniel J.); Barrett, C. L. (Christopher L.); Marathe, M. V. (Madhav V.) & Ravi, S. S. (Sekharipuram S.)
Partner: UNT Libraries Government Documents Department
open access

Sequential dynamical systems with threshold functions.

Description: A sequential dynamical system (SDS) (see [BH+01] and the references therein) consists of an undirected graph G(V,E) where each node {nu} {epsilon} V is associated with a Boolean state (s{sub {nu}}) and a symmetric Boolean function f{sub {nu}} (called the local transition function at {nu}). The inputs to f{sub {nu}} are s{sub {nu}} and the states of all the nodes adjacent to {nu}. In each step of the SDS, the nodes update their state values using their local transition functions in the order spe… more
Date: January 1, 2001
Creator: Barrett, C. L. (Christopher L.); Hunt, H. B.; Marathe, M. V. (Madhav V.); Ravi, S. S.; Rosenkrantz, D. J. (Daniel J.) & Stearns, R. E. (Richard E.)
Partner: UNT Libraries Government Documents Department
open access

Bicriteria network design problems

Description: We study several bicriteria network design problems phrased as follows: given an undirected graph and two minimization objectives with a budget specified on one objective, find a subgraph satisfying certain connectivity requirements that minimizes the second objective subject to the budget on the first. Define an ({alpha}, {beta})-approximation algorithm as a polynomial-time algorithm that produces a solution in which the first objective value is at most {alpha} times the budget, and the second… more
Date: December 31, 1994
Creator: Marathe, M. V.; Ravi, R.; Sundaram, R.; Ravi, S. S.; Rosenkrantz, D. J. & Hunt, H. B., III
Partner: UNT Libraries Government Documents Department
open access

Bicriteria Network Design Problems

Description: The authors study a general class of bicriteria network design problems. A generic problem in this class is as follows: Given an undirected graph and two minimization objectives (under different cost functions), with a budget specified on the first, find a subgraph from a given subgraph class that minimizes the second objective subject to the budget on the first. They consider three different criteria -- the total edge cost, the diameter and the maximum degree of the network. Here, they present… more
Date: November 20, 1997
Creator: Marathe, M. V.; Ravi, R.; Sundaram, R.; Ravi, S. S.; Rosenkrantz, D. J. & Hunt, H. B., III
Partner: UNT Libraries Government Documents Department
Back to Top of Screen