scientific article; zbMATH DE number 2079335

zbMath1094.68615MaRDI QIDQ4471290

Dieter Kratsch, Kurt Mehlhorn, Jeremy P. Spinrad, Ross M. McConnell

Publication date: 28 July 2004

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

recognition algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (18)

Optimal length resolution refutations of difference constraint systems ⋮ Improved Algorithms for Detecting Negative Cost Cycles in Undirected Graphs ⋮ On canonical forms for zero-sum stochastic mean payoff games ⋮ Graph classes with structured neighborhoods and algorithmic applications ⋮ Analyzing read-once cutting plane proofs in Horn systems ⋮ Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs ⋮ Connected permutation graphs ⋮ A new characterization of HH-free graphs ⋮ Strict chordal and strict split digraphs ⋮ Pipelined algorithms to detect cheating in long-term grid computations ⋮ Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs ⋮ Witness (Delaunay) graphs ⋮ Fully dynamic recognition algorithm and certificate for directed cographs ⋮ An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs ⋮ Localized and compact data-structure for comparability graphs ⋮ A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs ⋮ Parameterized and exact algorithms for finding a read-once resolution refutation in 2CNF formulas ⋮ On the lengths of tree-like and dag-like cutting plane refutations of Horn constraint systems. Horn constraint systems and cutting plane refutations

This page was built for publication: