Automata, Languages and Programming
From MaRDI portal
Publication:5716773
DOI10.1007/11523468zbMath1082.68866OpenAlexW2940595899WikidataQ56656999 ScholiaQ56656999MaRDI QIDQ5716773
Fabrizio Grandoni, Dieter Kratsch, Fedor V. Fomin
Publication date: 10 January 2006
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11523468
Nonnumerical algorithms (68W05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)
Related Items (39)
A Faster Algorithm for Dominating Set Analyzed by the Potential Method ⋮ Improved edge-coloring with three colors ⋮ An improved exact algorithm for the domatic number problem ⋮ Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG ⋮ A top-down approach to search-trees: Improved algorithmics for 3-hitting set ⋮ On Independent Sets and Bicliques in Graphs ⋮ Improved worst-case complexity for the MIN 3-SET COVERING problem ⋮ Computing optimal Steiner trees in polynomial space ⋮ Fast exact algorithm for \(L(2,1)\)-labeling of graphs ⋮ A Moderately Exponential Time Algorithm for Full Degree Spanning Tree ⋮ Exact Algorithms for Edge Domination ⋮ Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms ⋮ Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation ⋮ Exact algorithms for \(L(2,1)\)-labeling of graphs ⋮ An exact algorithm for connected red-blue dominating set ⋮ Branch and recharge: exact algorithms for generalized domination ⋮ On partitioning a graph into two connected subgraphs ⋮ When polynomial approximation meets exact computation ⋮ Turbo-Charging Dominating Set with an FPT Subroutine: Further Improvements and Experimental Analysis ⋮ Faster Steiner Tree Computation in Polynomial-Space ⋮ An exact algorithm for the minimum dominating clique problem ⋮ Fast Exact Algorithm for L(2,1)-Labeling of Graphs ⋮ When polynomial approximation meets exact computation ⋮ Solving connected dominating set faster than \(2^n\) ⋮ Exact algorithms for exact satisfiability and number of perfect matchings ⋮ On the minimum feedback vertex set problem: Exact and enumeration algorithms ⋮ Dominating sets in intersection graphs of finite groups ⋮ Finding a dominating set on bipartite graphs ⋮ Parameterized algorithms for \(d\)-hitting set: the weighted case ⋮ Improved upper bounds for vertex cover ⋮ Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs ⋮ Inexact graph matching using a hierarchy of matching processes ⋮ Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems ⋮ A bounded search tree algorithm for parameterized face cover ⋮ Efficiency in exponential time for domination-type problems ⋮ On two techniques of combining branching and treewidth ⋮ Counting Independent Sets in Claw-Free Graphs ⋮ Pathwidth of cubic graphs and exact algorithms ⋮ An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure
This page was built for publication: Automata, Languages and Programming
