Reducibility among Combinatorial Problems
From MaRDI portal
Publication:4999425
DOI10.1007/978-1-4684-2001-2_9zbMath1467.68065OpenAlexW2401610261WikidataQ110971675 ScholiaQ110971675MaRDI QIDQ4999425
Publication date: 6 July 2021
Published in: Complexity of Computer Computations (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-1-4684-2001-2_9
combinatorial problemTuring machinepolynomial timeregular expressionlanguage recognitionwords over a finite alphabet
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Discrete mathematics in relation to computer science (68Rxx) Classical models of computation (Turing machines, etc.) (68Q04)
Related Items (only showing first 100 items - show all)
Tighter estimates for \(\epsilon\)-nets for disks ⋮ Tractability in constraint satisfaction problems: a survey ⋮ On enumerating minimal siphons in Petri nets using CLP and SAT solvers: theoretical and practical complexity ⋮ Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique ⋮ Guessing games on triangle-free graphs ⋮ Minimum maximum reconfiguration cost problem ⋮ An \(O(n\log n)\) algorithm for finding edge span of cacti ⋮ A fast greedy sequential heuristic for the vertex colouring problem based on bitwise operations ⋮ On the directed cut cone and polytope ⋮ The online knapsack problem with incremental capacity ⋮ Nearly-perfect hypergraph packing is in NC ⋮ A generalization of chordal graphs and the maximum clique problem ⋮ Semi-intelligible Isar proofs from machine-generated proofs ⋮ Single-commodity robust network design with finite and hose demand sets ⋮ Sequential Monte Carlo for counting vertex covers in general graphs ⋮ Differential approximation results for the traveling salesman and related problems ⋮ Judicious partitions of weighted hypergraphs ⋮ Edge intersection graphs of \(L\)-shaped paths in grids ⋮ Circular convex bipartite graphs: feedback vertex sets ⋮ Unified encoding for hyper-heuristics with application to bioinformatics ⋮ A \(13k\)-kernel for planar feedback vertex set via region decomposition ⋮ Cost-sharing scheduling games on restricted unrelated machines ⋮ On determining if tree-based networks contain fixed trees ⋮ The label cut problem with respect to path length and label frequency ⋮ On the hardness of bribery variants in voting with CP-nets ⋮ Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games ⋮ On a new edge function on complete weighted graphs and its application for locating Hamiltonian cycles of small weight ⋮ Hamilton cycles in almost distance-hereditary graphs ⋮ An efficient two-stage algorithm for decentralized scheduling of micro-CHP units ⋮ A branch-and-cut framework for the consistent traveling salesman problem ⋮ Cycles and matchings in randomly perturbed digraphs and hypergraphs ⋮ Solving hard control problems in voting systems via integer programming ⋮ Fast heuristics for the frequency channel assignment problem in multi-hop wireless networks ⋮ An exact decomposition algorithm for the generalized knapsack sharing problem ⋮ Totally optimal decision trees for Boolean functions ⋮ Well-covered triangulations. IV ⋮ NP-completeness of the \(\{k \}\)-packing function problem in graphs ⋮ Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments ⋮ Computational complexity of manipulation: a survey ⋮ The assignment problem with nearly Monge arrays and incompatible partner indices ⋮ Scheduling with compressible and stochastic release dates ⋮ A Pareto-metaheuristic for a bi-objective winner determination problem in a combinatorial reverse auction ⋮ Ambulance routing for disaster response with patient groups ⋮ Memetic search for the max-bisection problem ⋮ Breakout local search for maximum clique problems ⋮ A nonmonotone GRASP ⋮ Alternating paths and cycles of minimum length ⋮ On the parameterized complexity of b-\textsc{chromatic number} ⋮ The constrained shortest path tour problem ⋮ Algorithmic aspects of open neighborhood location-domination in graphs ⋮ On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree ⋮ Directed Steiner trees with diffusion costs ⋮ GIS technology as an environment for testing an advanced mathematical model for optimization of road maintenance ⋮ The three-dimensional matching problem in kalmanson matrices ⋮ An adaptive multistart tabu search approach to solve the maximum clique problem ⋮ Compact DSOP and partial DSOP forms ⋮ Approximability of the vertex cover problem in power-law graphs ⋮ Approximation algorithms for orienting mixed graphs ⋮ A novel parameterised approximation algorithm for \textsc{minimum vertex cover} ⋮ Feedback vertex sets on restricted bipartite graphs ⋮ On the \(k\)-residue of disjoint unions of graphs with applications to \(k\)-independence ⋮ Average-case complexity of backtrack search for coloring sparse random graphs ⋮ Approximation with a fixed number of solutions of some multiobjective maximization problems ⋮ Minimum weight Euclidean \(t\)-spanner is NP-hard ⋮ A survey on offline scheduling with rejection ⋮ A note on reverse scheduling with maximum lateness objective ⋮ Erratum to: ``Minimizing total tardiness on parallel machines with preemptions ⋮ On judicious bisections of graphs ⋮ The unbiased black-box complexity of partition is polynomial ⋮ NP-hardness of the Euclidean Max-Cut problem ⋮ Enumerating minimal subset feedback vertex sets ⋮ The first international nurse rostering competition 2010 ⋮ Polynomial-time perfect matchings in dense hypergraphs ⋮ The complexity of the empire colouring problem ⋮ The kernelization complexity of connected domination in graphs with (no) small cycles ⋮ Computing on binary strings ⋮ Degree diameter problem on honeycomb networks ⋮ On the maximum acyclic subgraph problem under disjunctive constraints ⋮ The decycling number of generalized Petersen graphs ⋮ Computational complexity analysis of the sensor location flow observability problem ⋮ A heuristic, dynamic programming-based approach for a two-dimensional cutting problem with defects ⋮ Handelman's hierarchy for the maximum stable set problem ⋮ On the parameterized complexity of vertex cover and edge cover with connectivity constraints ⋮ Exploring the tractability border in epistemic tasks ⋮ The feedback arc set problem with triangle inequality is a vertex cover problem ⋮ Routing regardless of network stability ⋮ Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem ⋮ Weighted synergy graphs for effective team formation with heterogeneous ad hoc agents ⋮ Zero forcing number, constrained matchings and strong structural controllability ⋮ Bandwidth allocation in cellular networks with multiple interferences ⋮ Decycling bubble sort graphs ⋮ On the parameterized complexity of finding separators with non-hereditary properties ⋮ \textsc{Max-Cut} parameterized above the Edwards-Erdős bound ⋮ A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization ⋮ Convex optimization for the densest subgraph and densest submatrix problems ⋮ A characterization of triangle-free Gorenstein graphs and Cohen-Macaulayness of second powers of edge ideals ⋮ Approximately counting approximately-shortest paths in directed acyclic graphs ⋮ Parametric packing of selfish items and the subset sum algorithm ⋮ Parameterizations of test cover with bounded test sizes ⋮ Multi-rooted greedy approximation of directed Steiner trees with applications
This page was built for publication: Reducibility among Combinatorial Problems
