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
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, The bipartite margin shop and maximum red matchings free of blue-red alternating cycles, Minimizing the weighted number of tardy jobs on a single machine with release dates, Maximizing data locality in distributed systems, A threshold accepting heuristic with intense local search for the solution of special instances of the traveling salesman problem, A branch-and-bound based solution approach for the mixed-model assembly line-balancing problem for minimizing stations and task duplication costs, Two due date assignment problems in scheduling a single machine, Graph factors and factorization: 1985--2003: a survey, Patterns of quadratic residues and nonresidues for infinitely many primes, A derandomization using min-wise independent permutations, On reductions for the Steiner problem in graphs, Selection of programme slots of television channels for giving advertisement: a graph theoretic approach, MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs, On the asymptotic probabilistic analysis of scheduling problems in the presence of precedence constraints, First-order spectra with one variable, Covering a set with arithmetic progressions is NP-complete, The complexity of searching in \(X+Y\) and other multisets, The complexity of regular subgraph recognition, Coloring certain proximity graphs, Object-oriented interaction in resource constrained scheduling, A state-of-the-art review of parallel-machine scheduling research, Not being (super)thin or solid is hard: A study of grid Hamiltonicity, An improved lower bound for approximating minimum GCD multiplier in \(\ell _\infty \) norm (GCDM\(_\infty\)), A better differential approximation ratio for symmetric TSP, Probabilistic analysis for scheduling with conflicts, A generalization of the integer linear infeasibility problem, On a problem of integer optimization, A modified VNS metaheuristic for max-bisection problems, A discrete filled function algorithm for approximate global solutions of max-cut problems, On routing in VLSI design and communication networks, Partition into cliques for cubic graphs: Planar case, complexity and approximation, A model and heuristic algorithms for multi-unit nondiscriminatory combinatorial auction, George Dantzig's impact on the theory of computation, Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes, \(\varepsilon \)-optimization schemes and \(L\)-bit precision: alternative perspectives for solving combinatorial optimization problems, The Steiner tree problem on graphs: inapproximability results, Random assignment problems, Dynamic evolution of economically preferred facilities, Edge ranking and searching in partial orders, Improved algorithms for feedback vertex set problems, Nash equilibria in discrete routing games with convex latency functions, Colorings at minimum cost, Inequalities for entropy-based measures of network information content, A new clustering algorithm for coordinate-free data, Maximum cut in fuzzy nature: models and algorithms, On well-covered triangulations. II., Optimal cuts in graphs and statistical mechanics, Solving a cut problem in bipartite graphs by linear programming: application to a forest management problem, On well-covered triangulations. III, On the complexity of finding gapped motifs, The computational complexity of rationalizing behavior, An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring, Bounds for pairs in partitions of graphs, Complexity results related to monophonic convexity, Satisfiability of algebraic circuits over sets of natural numbers, On packing shortest cycles in graphs, Counting the number of vertex covers in a trapezoid graph, Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems, Joint ground and air emergency medical services coverage models: a greedy heuristic solution approach, On the enumeration of certain weighted graphs, The labeled maximum matching problem, Approximation algorithm for maximum edge coloring, Combinatorial algorithms for feedback problems in directed graphs, Detecting critical nodes in sparse graphs, On the complexity of finding balanced oneway cuts, Linear time self-stabilizing colorings, A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems, Geometric quadrisection in linear time, with application to VLSI placement, Matrix columns allocation problems, Efficient approximation of Min Set Cover by moderately exponential algorithms, Threshold and complexity results for the cover pebbling game, Vertex and edge covers with clustering properties: Complexity and algorithms, Single machine scheduling and due date assignment with positionally dependent processing times, Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation, On selecting a maximum volume sub-matrix of a matrix and related problems, On the longest common parameterized subsequence, The submodular knapsack polytope, PTAS for connected vertex cover in unit disk graphs, A search space ``cartography for guiding graph coloring heuristics, Covering the edges of bipartite graphs using \(K_{2,2}\) graphs, A survey on the complexity of tournament solutions, On the complexity of Slater's problems, Canonical finite state machines for distributed systems, Models for concurrent product and process design, A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurse rostering problems, A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs, Performance evaluation of concurrent systems using Petri nets, On a simple deadlock recovery problem, The optimum assignments and a new heuristic approach for the traveling salesman problem, A normal form for arithmetical representation of \({\mathcal N}{\mathcal P}\)-sets, Characterizations and computational complexity of systolic trellis automata, Optimal multiway search trees for variable size keys, Edge-contraction problems, Using a facility location algorithm to solve large set covering problems, Minimum deviation and balanced optimization: A unified approach, Bibliography on domination in graphs and some basic definitions of domination parameters, On the complexity of scheduling unit-time jobs with or-precedence constraints, No-wait flexible flowshop scheduling with no-idle machines, Establishing motion correspondence using extended temporal scope, The complexity of constraint satisfaction problems for small relation algebras, Solving \(7\times 7\) hex with domination, fill-in, and virtual connections, Unit disk graphs, On minimum dominating sets with minimum intersection, On the complexity of generalized due date scheduling problems, Exact colouring algorithm for weighted graphs applied to timetabling problems with lectures of different lengths, Finding optimal derivation strategies in redundant knowledge bases, Improved bounds for harmonic-based bin packing algorithms, Single step graph search problem, The synchronization problem in protocol testing and its complexity, Some results concerning the complexity of restricted colorings of graphs, Optimization, approximation, and complexity classes, On the minimization of the weighted number of tardy jobs with random processing times and deadline, On the theory of average case complexity, On the design of replicated databases, Integer programs for logic constraint satisfaction, On polynomial-time Turing and many-one completeness in PSPACE, The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory, On simulation and optimization of macroeconometric models, Optimal due-date assignment and sequencing, An approximation algorithm for the general routing problem, Computation of Hilbert functions, The algorithmic complexity of colour switching, An algorithm for min-cost edge-disjoint cycles and its applications, Processor optimization for flow graphs, Minimum perfect bipartite matchings and spanning trees under categorization, The multicovering problem, Operational estimators for the length of a traveling salesman tour, An approximation algorithm for the asymmetric travelling salesman problem with distances one and two, Approximation algorithms for combinatorial problems, On cubical graphs, A versatile system for computer-controlled assembly, Bounds for 3-matroid intersection problems, The membership question for ETOL-languages is polynomially complete, A linear algorithm for the domination number of a tree, NP-complete scheduling problems, A class of facet producing graphs for vertex packing polyhedra, Space-bounded reducibility among combinatorial problems, The NP-completeness of the bandwidth minimization problem, A comparison of polynomial time reducibilities, A linear algorithm for the Hamiltonian completion number of a tree, Representation of structured events and efficient procedures for their recognition, Some simplified NP-complete graph problems, A lower bound on the number of additions in monotone computations, Relative complexity of checking and evaluating, A characterization of the power of vector machines, Intersection graphs of curves in the plane, Riemann's hypothesis and tests for primality, Complete problems for deterministic polynomial time, The polynomial-time hierarchy, Data analysis implications of some concepts related to the cuts of a graph, Complexity-class-encoding sets, Sparse complex polynomials and polynomial reducibility, Approximate algorithms for some generalized knapsack problems, A graph model for scheduling processes in systems with parallel computations, Complexity of some problems in Petri nets, Almost integral polyhedra related to certain combinatorial optimization problems, Efficient Algorithms for (3,1) Graphs, One more polynomial complete consecutive retrieval problem, Complete sets and the polynomial-time hierarchy, The dependence graph for bases in matroids, NP-complete decision problems for binary quadratics, Die Zeitkomplexität des Normalisierungsproblems bei kontextsensitiven Grammatiken, A language and a program for stating and solving combinatorial problems, Subgraph isomorphism, matching relational structures and maximal cliques, Nondeterminism and Boolean operations in pda's, On graphs with Hamiltonian squares, On the complexity of some two-person perfect-information games, Resource constrained scheduling as generalized bin packing, On the complexity of regular resolution and the Davis-Putnam procedure, On log-tape isomorphisms of complete sets, The distribution of 1-widths of (0,1)-matrices, The Euclidean traveling salesman problem is NP-complete, A linear-time algorithm for finding all feedback vertices, Candidate keys for relations, A recognition algorithm for the intersection graphs of paths in trees, The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two, Deadline scheduling of tasks with ready times and resource constraints, An algorithm and efficient data structures for the binary knapsack problem, Graph isomorphism, general remarks, Complexity in mechanized hypothesis formation, Even initial feedback vertex set problem is NP-complete, Efficient search for rationals, Graph 2-isomorphism is NP-complete, Electronic circuit diagnostic expert systems - a survey, The complexity of generalized clique covering, Minimization of resource consumption under a given deadline in the two- processor flow-shop scheduling problem, Strong nondeterministic Turing reduction - a technique for proving intractability, An adaptive, multiple restarts neural network algorithm for graph coloring, Approximations for the disjoint paths problem in high-diameter planar networks, Classifying molecular sequences using a linkage graph with their pairwise similarities, Class Steiner trees and VLSI-design, A complete anytime algorithm for number partitioning, An adaptation of SH heuristic to the location set covering problem, Generalized \(p\)-center problems: Complexity results and approximation algorithms, A heuristic algorithm for the mini-max spanning forest problem, Geometric three-dimensional assignment problems, Single machine earliness and tardiness scheduling, Linear programs for constraint satisfaction problems, The complexity of some problems related to GRAPH 3-COLORABILITY, Exploration of NP-hard enumeration problems by simulated annealing -- the spectrum values of permanents, Impact of learning and fatigue factors on single machine scheduling with penalties for tardy jobs, Length-bounded disjoint paths in planar graphs, Edge-disjoint packings of graphs, Approximation algorithms for multi-dimensional assignment problems with decomposable costs, Local optima topology for the \(k\)-coloring problem, A primal-dual approximation algorithm for the Steiner forest problem, Optimal mapping in direct mapped cache environments, An approximation algorithm for the license and shift class design problem, Complexity of a class of nonlinear combinatorial problems related to their linear counterparts, Periodic assignment and graph colouring, Bounded degree graph inference from walks, Polyhedral structure and properties of a model for layout design, Unrelated parallel machine scheduling using local search, Some complexity results in cyclic scheduling, Finding Hamiltonian circuits in arrangements of Jordan curves is NP- complete, Earliness-tardiness scheduling problems with a common delivery window, A data structure for bicategories, with application to speeding up an approximation algorithm, Scheduling with batching: Minimizing the weighted number of tardy jobs, One-machine generalized precedence constrained scheduling problems, Single-machine scheduling to minimize the weighted number of early and tardy agreeable jobs, On the complexity of some basic problems in computational convexity. I. Containment problems, Probabilistically checkable proofs and their consequences for approximation algorithms, Optimally balancing assembly lines with different workstations, On enumerating all minimal solutions of feedback problems, Phylogenetic diversity and biodiversity indices on phylogenetic networks, On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs, New results on the computation of median orders, The hardness of approximate optima in lattices, codes, and systems of linear equations, Computation of Hilbert-Poincaré series, A local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search, An effective iterated tabu search for the maximum bisection problem, Distributed multicast routing in point-to-point networks, Interior-point methods: An old and new approach to nonlinear programming, Spectrum graph coloring and applications to Wi-Fi channel assignment, Solving large set covering problems for crew scheduling, Infinite versions of some problems from finite complexity theory, Complexity of searching an immobile hider in a graph, Approximating the independence number via the \(\vartheta\)-function, General stochastic single-machine scheduling with regular cost functions, A bound for the symmetric travelling salesman problem through matroid formulation, Graph theoretic relaxations of set covering and set partitioning problems, Edge ranking of graphs is hard, Is a unit-job shop not easier than identical parallel machines?, On certain polytopes associated with graphs, A hierarchy for nondeterministic time complexity, Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity, Motion tracking as a constrained optimization problem., On the complexity of compressing two dimensional routing tables with order, On well-covered triangulations. I, Inverting onto functions., Large induced forests in planar graphs with girth 4, On the approximate tradeoff for bicriteria batching and parallel machine scheduling problems., Multi-objective design of team oriented assembly systems., New bounds for the signless Laplacian spread, Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge, Optimization over structured subsets of positive semidefinite matrices via column generation, An efficient solution method to design the cost-minimizing platform portfolio, PUSH: A generalized operator for the maximum vertex weight clique problem, Models for the piecewise linear unsplittable multicommodity flow problems, Mind the gap: a study of tube tour, Cliques with maximum/minimum edge neighborhood and neighborhood density, An exact approach for scheduling jobs with regular step cost functions on a single machine, Minimization of ordered, symmetric half-products, Complexity of the directed spanning cactus problem, Single machine preemptive scheduling with fixed jobs to minimize tardiness related criteria, A graph-oriented approach for the minimization of the number of late jobs for the parallel machines scheduling problem, Hybrid heuristics for examination timetabling problem, Balanced vertex-orderings of graphs, Improved haplotype assembly using Xor genotypes, What is the best greedy-like heuristic for the weighted set covering problem?, Selecting and covering colored points, The allocation problem in hardware design, Transfer flow graphs, A faster approximation algorithm for the Steiner tree problem in graphs, Recognizing renamable generalized propositional Horn formulas is NP- complete, Resolution deduction to detect satisfiability for another class including non-Horn sentences in propositional logic, ``Global graph problems tend to be intractable, Bandwidth contrained NP-complete problems, An algebraic point of view of the data structures of database systems, Interval vertex-coloring of a graph with forbidden colors, On the supermodular knapsack problem, König-Egerváry graphs, 2-bicritical graphs and fractional matchings, A selected tour of the theory of identification matrices, Minimal separating sets for acceptance conditions in Muller automata, Sequential colorings and perfect graphs, Neural and delay based heuristics for the Steiner problem in networks, A weighted graph polynomial from chromatic invariants of knots, Approximating minimum feedback vertex sets in hypergraphs, Counting stable sets on Cartesian products of graphs, The line index and minimum cut of weighted graphs, Minimal approximate hitting sets and rule templates, Interval edge coloring of a graph with forbidden colors, Dynamic scheduling of stochastic jobs on a single machine, Parallel machine scheduling to minimize costs for earliness and number of tardy jobs, Experiments with parallel branch-and-bound algorithms for the set covering problem, Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem, On approximability of the independent/connected edge dominating set problems, Nonpreemptive flowshop scheduling with machine dominance, Efficient approximation algorithms for the subset-sums equality problem., Extending matchings in claw-free graphs, Minimizing the expected number of tardy jobs when processing times are normally distributed, An introduction to the analysis of approximation algorithms, Some no-wait shops scheduling problems: Complexity aspect, Applications of scheduling theory to formal language theory, On the construction of parallel computers from various basis of Boolean functions, The principle of optimality in the design of efficient algorithms, Representability in mixed integer programming. I: Characterization results, A two-process implicit enumeration algorithm for the simple assembly line balancing problem, DB2 and DB2A: Two useful tools for constructing Hamiltonian circuits, An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines, A note on the average-case behavior of a simple differencing method for partitioning, Minimizing the expected weighted number of tardy jobs in stochastic flow shops, A note on complete problems for complexity classes, Solving large set covering problems on a personal computer, Bin packing problems in one dimension: Heuristic solutions and confidence intervals, On the complexity of the maximum satisfiability problem for Horn formulas, Some results and experiments in programming techniques for propositional logic, A two-machine flow shop scheduling problem with controllable job processing times, The complexity of optimization problems, Parallelism and the feedback vertex set problem, LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation, On the relative complexity of hard problems for complexity classes without complete problems, Probabilistic construction of deterministic algorithms: approximating packing integer programs, On locating minimum feedback vertex sets, Feasible arithmetic computations: Valiant's hypothesis, Worst-case performance of Rayward-Smith's Steiner tree heuristic, Graph isomorphism is in the low hierarchy, Subspaces with well-scaled frames, Positive relativizations of the \(P=?\) NP problem, Rudimentary relations and primitive recursion: A toolbox, Efficient delay routing, On the complexity of the robust stability problem for linear parameter varying systems, Tautology testing with a generalized matrix reduction method, Systems of distinct representatives for k families of sets, Complexity of Boolean algebras, Degree switching operations in networks and large scale systems assignment problems, On finding minimal length superstrings, Fast probabilistic algorithms for Hamiltonian circuits and matchings, Ranking arborescences in O(Km log n) time, Structure preserving reductions among convex optimization problems, Toward a unified approach for the classification of NP-complete optimization problems, Relational consistency algorithms and their application in finding subgraph and graph isomorphisms, Combinatorial problems over power sets, Lower bounds on the size of sweeping automata, Complexity of spanning tree problems: Part I, Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete, Storage allocation is NP-hard, Solving the resource constrained deadline scheduling problem via reduction to the network flow problem, A comparative study of approaches to dynamic location problems, The complexity of the equivalence problem for two characterizations of Presburger sets, On gamma-reducibility versus polynomial time many-one reducibility, A product positioning model with costs and prices, Non deterministic polynomial optimization problems and their approximations, Complexity of graph embeddability problems, On the complexity of scheduling jobs on dedicated resources to minimize set-up costs, Heuristics and their design: A survey, Fast approximation algorithm for job sequencing with deadlines, A branch and bound algorithm for the acyclic subgraph problem, Record allocation for minimizing seek delay, The shortest common supersequence problem over binary alphabet is NP- complete, On the complexity of simplifying quadratic forms, Probabilistic analysis of solving the assignment problem for the traveling salesman problem, On the Ferrers dimension of a digraph, Complexity of representation of graphs by set systems, General approximation algorithms for some arithmetical combinatorial problems, On the complexity of edge labelings for trees, Some results on relativized deterministic and nondeterministic time hierarchies, On the structure of sets in NP and other complexity classes, Chromatic optimisation: Limitations, objectives, uses, references, The communality problem for Stieltjes matrices, Optimal cocircuits in regular matroids and applications, A note on sparse oracles for NP, On the relationship between the biconnectivity augmentation and traveling salesman problems, The complexity of recognizing 3NF relation schemes, An NP-complete matching problem, Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis, A graph theoretic approach to switching function minimization, Directed maximal-cut problems, The edge Hamiltonian path problem is NP-complete, An arithmetical characterization of NP, An appraisal of computational complexity for operations researchers, The complexity of controlled selection, Dominating sets in perfect graphs, Strong nondeterministic polynomial-time reducibilities, On the complexity of partitioning graphs into connected subgraphs, Graph isomorphism problem, A note on the complexity of finding regular subgraphs, Clustering to minimize the maximum intercluster distance, The complexity of facets (and some facets of complexity), Analysis of a linear programming heuristic for scheduling unrelated parallel machines, New NP-hard and NP-complete polynomial and integer divisibility problems, Convergence of optimal stochastic bin packing, Robust algorithms: a different approach to oracles, Exposure to deadlock for communicating processes is hard to detect, Trapdoor knapsacks without superincreasing structure, Finding Hamiltonian circuits in interval graphs, A formal model of diagnostic inference. I. Problem formulation and decomposition, A formal model of diagnostic inference. II. Algorithmic solution and application, \(K_ i\)-covers. I: Complexity and polytopes, Verifying nonrigidity, An algorithm for the periodic solutions in the knapsack problem, Unnamed Item, On computational complexity of length embeddability of graphs, Completeness for nondeterministic complexity classes, Harmonious coloring: parameterized algorithms and upper bounds, Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey, On the complexity of bounded time and precision reachability for piecewise affine systems, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation, Separation algorithms for 0-1 knapsack polytopes, A short technical paper: Determining whether a vote assignment is dominated, Minimizing weighted number of tardy jobs and weighted earliness-tardiness penalties about a common due date, Online Admission Control and Embedding of Service Chains, Best location of service centers in a treelike network under budget constraints, Deadlocks and traps in Petri nets as Horn-satisfiability solutions and some related polynomially solvable problems, Unnamed Item, Extended and discretized formulations for the maximum clique problem, Unnamed Item, Open shop scheduling with delays, Unnamed Item, Unnamed Item, The Minimal Hitting Set Generation Problem: Algorithms and Computation, Convex Partitions of Graphs, On the complexity of feedback set problems in signed digraphs, Worst case analysis of two heuristics for the set partitioning problem, Convergence and Correctness of Max-Product Belief Propagation for Linear Programming, A Lower Bound of the cd-Chromatic Number and Its Complexity, A new solvable case of the traveling salesman problem, Minimal Multiset Grammars for Recurrent Dynamics, The travelling salesman problem and a class of polyhedra of diameter two, A geometrical method in combinatorial complexity, Domination When the Stars Are Out, Unnamed Item, Unnamed Item, Finding Temporal Paths Under Waiting Time Constraints., On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs, On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs, Lineare Charakterisierungen von Travelling Salesman Problemen, Some theoretical implications of local optimization, The complexity of linear programming, Single Machine Preemptive Scheduling to Minimize the Weighted Number of Late Jobs with Deadlines and Nested Release/Due Date Intervals, A constraint programming approach to cutset problems, Worst-case performance of Wong's Steiner tree heuristic, A branch-and-cut algorithm for graph coloring, On the probabilistic minimum coloring and minimum \(k\)-coloring, A Logical Approach to Hamiltonian Graphs, Drift analysis and average time complexity of evolutionary algorithms, NP-completeness for calculating power indices of weighted majority games, A modified greedy algorithm for dispersively weighted 3-set cover, On the facial structure of set packing polyhedra, More pathological examples for network flow problems, New facets of the STS polytope generated from known facets of the ATS polytope, TSP with bounded metrics, A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem, Scheduling two-stage hybrid flow shop with availability constraints, A comparison of Steiner tree relaxations, Edmonds polytopes and a hierarchy of combinatorial problems. (Reprint), Approximation algorithms for the bi-criteria weighted MAX-CUT problem, A polynomially solvable special case of the unbounded knapsack problem, Optimal arrangement of data in a tree directory, How to whack moles, Approximating the minimum clique cover and other hard problems in subtree filament graphs, A fixed-parameter-tractable algorithm for set packing, Algorithm for optimal winner determination in combinatorial auctions, The cd-Coloring of Graphs, Community detection in dense random networks, Algorithms for minclique scheduling problems, Minimizing the number of tardy jobs with precedence constraints and agreeable due dates, A fast approximation algorithm for solving the complete set packing problem, Theoretical and computational advances for network diversion, Optimal state amalgamation is NP-hard, The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme, Spectral bounds for the maximum cut problem, A method for the solution of monotonic integer linear programming problems, Differential approximation of NP-hard problems with equal size feasible solutions, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances, On the Existence of Tree Backbones that Realize the Chromatic Number on a Backbone Coloring, Switching Graphs, Randomized parallel algorithms for the multidimensional assignment problem, On the computational complexity of Longley's \(H\) functional, Incorporating kin selection in simulated annealing algorithm and its performance evaluation, Edmonds polytopes and a hierarchy of combinatorial problems, Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals, The complexity of the word problems for commutative semigroups and polynomial ideals, Efficient graph automorphism by vertex partitioning, The simple plant location problem: Survey and synthesis, Some NP-complete problems in linear programming, \(NP\)-hardness of linear multiplicative programming and related problems, Structure and complexity of extreme Nash equilibria, The 2004 Benjamin Franklin medal in computer and cognitive science presented to Richard M. Karp, Perfect Digraphs, Constructing arbitrarily large graphs with a specified number of Hamiltonian cycles, On the distributed decision-making complexity of the minimum vertex cover problem, Polynomial algorithms for a class of linear programs, Algorithm of determination of largest internally stable set of a graph, A class of polynomially solvable range constraints for interval analysis without widenings, Change ringing and Hamiltonian cycles: The search for Erin and Stedman triples, On the complexity of some hop domination parameters, Solving maximum independent set by asynchronous distributed hopfield-type neural networks, Modal Expressiveness of Graph Properties, A hypergraph version of the Gallai-Edmonds Theorem, Trivial integer programs unsolvable by branch-and-bound, Uniformly hard languages., Towards optimal lower bounds for clique and chromatic number., Approximate and dynamic rank aggregation, Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem, On the hardness of the minimum height decision tree problem, NP-completeness in hedonic games, On the complexity of the \(k\)-customer vehicle routing problem, On-line generalized Steiner problem, Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday), Simplex-stochastic collocation method with improved scalability, All roads lead to Rome -- new search methods for the optimal triangulation problem, Monge matrices make maximization manageable, Scheduling shops to minimize the weighted number of late jobs, The reversing number of a digraph, On component-size bounded Steiner trees, On the integral dicycle packings and covers and the linear ordering polytope, Approximation schemes for a class of subset selection problems, A survey of scheduling with controllable processing times, On specifying Boolean functions by labelled examples, Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs, The shifting algorithm technique for the partitioning of trees, Solving the max-cut problem using eigenvalues, Two situations with unit-cost: ordered abelian semi-groups and some commutative rings, Ranking of decision rules with random power distribution, Heterogeneous-criteria scheduling: Minimizing weighted number of tardy jobs and weighted completion time, A 2-approximation NC algorithm for connected vertex cover and tree cover, Approximate linear algebra is intractable, A multi-stage IP-based heuristic for class timetabling and trainer rostering, Robust Hamiltonicity of random directed graphs, A computationally intractable problem on simplicial complexes, Three-dimensional axial assignment problems with decomposable cost coefficients, Algorithmic aspects of the generalized clique-transversal problem on chordal graphs, Single machine scheduling to minimize the number of early and tardy jobs, Finding a maximum compatible tree is NP-hard for sequences and trees, Exact solution of the 2-dimensional grid arrangement problem, Equitable coloring of hypergraphs, Tracking paths, FPGA implementation of a stochastic neural network for monotonic pseudo-Boolean optimization, Weighted improper colouring, Strengthening hash families and compressive sensing, Improved approximation bounds for the minimum rainbow subgraph problem, Intractability of min- and max-cut in streaming graphs, Faster algorithm for optimum Steiner trees, The stochastic U-line balancing problem: a heuristic procedure, Multi-objective metaheuristics for a location-routing problem with multiple use of vehicles on real data and simulated data, A branch-and-bound algorithm to solve the linear ordering problem for weighted tournaments, Factor models on locally tree-like graphs, A VNS metaheuristic with stochastic steps for Max 3-cut and Max 3-section, Geometric buildup algorithms for sensor network localization, Improved non-approximability results for minimum vertex cover with density constraints, Concerning existential definition of the class \(NP\): Theoretical analysis of an alternative approach, On independence numbers of distance graphs with vertices in \(\{-1,0,1\}^n\): estimates, conjectures, and applications to the Nelson-Erdős-hadwiger problem and the borsuk problem, Graph isomorphism and identification matrices: Sequential algorithms, Complexity of constructing solutions in the core based on synergies among coalitions, MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability, On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints, Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs, Trading grid services - a multi-attribute combinatorial approach, A cutting plane algorithm for graph coloring, On the tour partitioning heuristic for the unit demand capacitated vehicle routing problem, Solving a bi-objective transportation location routing problem by metaheuristic algorithms, Triangle-free subcubic graphs with minimum bipartite density, A new approach to the learning effect: Beyond the learning curve restrictions, Reductions, completeness and the hardness of approximability, A well-solvable special case of the bounded knapsack problem, Minimum \(k\)-path vertex cover, Heuristics for scheduling unrelated parallel machines, Complexity of a 3-dimensional assignment problem, Bin packing and multiprocessor scheduling problems with side constraint on job types, On the NP-hardness of edge-deletion and -contraction problems, On clique covers and independence numbers of graphs, Combining traveling salesman and traveling repairman problems: a multi-objective approach based on multiple scenarios, Graphenalgorithmen und Überdeckungsprobleme, Fast algorithms for bin packing, Deciding \(k\)-colorability in expected polynomial time, On approximation of max-vertex-cover, A characterization of weakly bipartite graphs, On the algorithmic complexity of determining the AVD and NSD chromatic indices of graphs, Steiner trees in uniformly quasi-bipartite graphs., On the terminal Steiner tree problem., Off-line temporary tasks assignment., How hard is computing the edit distance?, A completeness theory for polynomial (Turing) kernelization, Universally balanced combinatorial optimization games, Is your model checker on time? On the complexity of model checking for timed modal logics, Steiner's problem in double trees, Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties, Speeding up a memetic algorithm for the max-bisection problem, Minimizing the weighted number of tardy jobs on a single machine, A fuzzy genetic algorithm for driver scheduling, Finding similar regions in many sequences, On local search for the generalized graph coloring problem, A cross-border transportation system under supply and demand constraints
