Automata, Languages and Programming

DOI10.1007/b99859zbMath1098.68094OpenAlexW2505584480MaRDI QIDQ5466464

Sanjeev Khanna, Andreas Björklund, Thore Husfeldt

Publication date: 24 August 2005

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/b99859

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (18)

An approximation algorithm for the longest cycle problem in solid grid graphs ⋮ Integer programming formulations for the elementary shortest path problem ⋮ Formally verified algorithms for upper-bounding state space diameters ⋮ Evaluation and Enumeration Problems for Regular Path Queries ⋮ Inapproximability of shortest paths on perfect matching polytopes ⋮ Finite Automata, Digraph Connectivity, and Regular Expression Size ⋮ Unnamed Item ⋮ The negative cycles polyhedron and hardness of checking some polyhedral properties ⋮ On structured output training: hard cases and an efficient alternative ⋮ The Maximum Binary Tree Problem. ⋮ Finding large cycles in Hamiltonian graphs ⋮ Towards better models of externalities in sponsored search auctions ⋮ On the complexity of finding internally vertex-disjoint long directed paths ⋮ Divergence and quasi-isometry classes of random Gromov’s monsters ⋮ The maximum binary tree problem ⋮ Path-Based Mathematical Morphology on Tensor Fields ⋮ A note on the approximability of deepest-descent circuit steps ⋮ On a simple randomized algorithm for finding a 2-factor in sparse graphs

This page was built for publication: Automata, Languages and Programming