Bounded degree interval sandwich problems

DOI10.1007/PL00009277zbMath0934.68070MaRDI QIDQ1293876

Ron Shamir, Haim Kaplan

Publication date: 3 April 2000

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

intervalizing colored graphsinterval sandwich

Mathematics Subject Classification ID

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

Related Items (12)

The graph sandwich problem for 1-join composition is NP-complete ⋮ Improved Lower Bounds for Graph Embedding Problems ⋮ On decision and optimization (\(k\),\(l\))-graph sandwich problems ⋮ The pair completion algorithm for the homogeneous set sandwich problem ⋮ The external constraint 4 nonempty part sandwich problem ⋮ Near-optimal solutions for the generalized max-controlled set problem ⋮ Complexity classification of some edge modification problems ⋮ The sandwich problem for cutsets: clique cutset, \(k\)-star cutset ⋮ An improved derandomized approximation algorithm for the max-controlled set problem ⋮ On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs ⋮ The graph sandwich problem for \(P_4\)-sparse graphs ⋮ Exact algorithms for intervalizing coloured graphs

This page was built for publication: Bounded degree interval sandwich problems