scientific article; zbMATH DE number 3571502
From MaRDI portal
Publication:4142699
zbMath0366.68041MaRDI QIDQ4142699
Publication date: 1975
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)
Related Items (only showing first 100 items - show all)
Partially dynamic bin packing can be solved within \(1 + \varepsilon\) in (amortized) polylogarithmic time ⋮ On universal learning algorithms ⋮ Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs ⋮ Improved performance of the greedy algorithm for partial cover ⋮ A lower bound on the order of the largest induced forest in planar graphs with high girth ⋮ Hub location under competition ⋮ An enhanced branch-and-bound algorithm for the talent scheduling problem ⋮ Compressing two-dimensional routing tables with order ⋮ A minimized-rule based approach for improving data currency ⋮ On the distance and multidistance graph embeddability problem ⋮ A practical greedy approximation for the directed Steiner tree problem ⋮ Graph properties checkable in linear time in the number of vertices ⋮ The complexity of computing the permanent ⋮ On several partitioning problems of Bollobás and Scott ⋮ A complete one-way function based on a finite rank free \(\mathbb{Z}\times\mathbb{Z}\)-module ⋮ Dynamics and control at feedback vertex sets. I: Informative and determining nodes in regulatory networks ⋮ A survey of single machine scheduling to minimize weighted number of tardy jobs ⋮ On the complexity of deciding avoidability of sets of partial words ⋮ On the Pólya permanent problem over finite fields ⋮ Optimal detection of sparse principal components in high dimension ⋮ The complexity of free-flood-it on \(2\times n\) boards ⋮ Small bipartite subgraph polytopes ⋮ Revisiting the complexity of and/or graph solution ⋮ Multitask \(n\)-vehicle exploration problem: complexity and algorithm ⋮ Risk models for the prize collecting Steiner tree problems with interval data ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ Holographic algorithms: from art to science ⋮ Compactly representing utility functions using weighted goals and the Max aggregator ⋮ Gap inequalities for non-convex mixed-integer quadratic programs ⋮ The most vital nodes with respect to independent set and vertex cover ⋮ Analysis of an iterated local search algorithm for vertex cover in sparse random graphs ⋮ An investigation into two bin packing problems with ordering and orientation implications ⋮ Guarding a set of line segments in the plane ⋮ Approximation algorithms for a geometric set cover problem ⋮ Uniform unweighted set cover: the power of non-oblivious local search ⋮ Optimization of stowage plans for RoRo ships ⋮ General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems ⋮ Information-theoretic approaches to branching in search ⋮ Most probable explanations in Bayesian networks: complexity and tractability ⋮ On the bounds of feedback numbers of \((n,k)\)-star graphs ⋮ Complexity results for the gap inequalities for the max-cut problem ⋮ Group scheduling with deteriorating jobs to minimize the total weighted number of late jobs ⋮ NP-completeness and APX-completeness of restrained domination in graphs ⋮ Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem ⋮ The maximum degree and diameter-bounded subgraph in the mesh ⋮ A polynomial-time recursive algorithm for some unconstrained quadratic optimization problems ⋮ Hamiltonian properties of locally connected graphs with bounded vertex degree ⋮ Algorithmic aspects of \(k\)-tuple total domination in graphs ⋮ Graph clustering ⋮ Randomly colouring graphs (a combinatorial view) ⋮ A survey on the structure of approximation classes ⋮ Dominating set is fixed parameter tractable in claw-free graphs ⋮ Scheduling semiconductor multihead testers using metaheuristic techniques embedded with lot-specific and configuration-specific information ⋮ An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes ⋮ Complexity of counting cycles using zeons ⋮ A note on approximation of the vertex cover and feedback vertex set problems -- Unified approach ⋮ On-line versus off-line computation in dynamic text compression ⋮ Cook versus Karp-Levin: Separating completeness notions if NP is not small ⋮ Succinct circuit representations and leaf language classes are basically the same concept ⋮ On the acceptance power of regular languages ⋮ Restrictions of graph partition problems. I ⋮ Linear bounds for on-line Steiner problems ⋮ The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness ⋮ Filling gaps in the boundary of a polyhedron ⋮ Price of anarchy for graph coloring games with concave payoff ⋮ A linear-time algorithm for computing the intersection of all odd cycles in a graph ⋮ Reducing the generalised Sudoku problem to the Hamiltonian cycle problem ⋮ A multiple search operator heuristic for the max-k-cut problem ⋮ Linear-space best-first search ⋮ Minimizing the number of tardy jobs in single machine sequencing ⋮ A shifting algorithm for constrained min-max partition on trees ⋮ A fast and effective heuristic for the feedback arc set problem ⋮ Finite-model theory -- A personal perspective ⋮ Feasibility problems for recurring tasks on one processor ⋮ Reachability computation for polynomial dynamical systems ⋮ Non-standard approaches to integer programming ⋮ Pseudo-Boolean optimization ⋮ Selected topics on assignment problems ⋮ A simple proof of an inequality connecting the alternating number of independent sets and the decycling number ⋮ The full Steiner tree problem ⋮ Finding odd cycle transversals. ⋮ Two-constraint domain decomposition with space filling curves ⋮ Computational complexity of the problem of tree generation under fine-grained access control policies ⋮ Survey of polynomial transformations between NP-complete problems ⋮ Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s) ⋮ A heuristic approach for the travelling purchaser problem ⋮ Kernelization hardness of connectivity problems in \(d\)-degenerate graphs ⋮ Rainbow graph splitting ⋮ Membership for growing context-sensitive grammars is polynomial ⋮ Ordered vertex removal and subgraph problems ⋮ Median linear orders: Heuristics and a branch and bound algorithm ⋮ A min-max relation for stable sets in graphs with no odd-\(K_ 4\) ⋮ On the distribution of the domination number for random class cover catch digraphs ⋮ Cook reducibility is faster than Karp reducibility in NP ⋮ Heuristically guided algorithm for k-parity matroid problems ⋮ On approximation problems related to the independent set and vertex cover problems ⋮ Applications of edge coverings by cliques ⋮ Exploring further advantages in an alternative formulation for the set covering problem ⋮ Worst-case analysis of two travelling salesman heuristics ⋮ Transforming asymmetric into symmetric traveling salesman problems
This page was built for publication:
