Bounded degree interval sandwich problems

DOI10.1007/PL00009277MaRDI QIDQ1293876zbMATH OpenFDO

Authors Haim Kaplan, Ron Shamir

Publication date 3 April 2000

Published in Algorithmica (Search for Journal in Brave)

zbMATH Keywords

interval sandwichintervalizing colored graphs

Mathematics Subject Classification ID

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

Recommendations

• On intervalizing \(k\)-colored graphs for DNA physical mapping
• Intervalizing \(k\)-colored graphs
• The hardness of intervalizing four colored caterpillars
• Complexity and algorithms for graph and hypergraph sandwich problems

Cited in

(15)

• On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
• The graph sandwich problem for \(P_4\)-sparse graphs
• The external constraint 4 nonempty part sandwich problem
• scientific article; zbMATH DE number 6423755 (Why is no real title available?)
• A sandwich with segment convexity
• Near-optimal solutions for the generalized max-controlled set problem
• Complexity classification of some edge modification problems
• Exact algorithms for intervalizing coloured graphs
• The graph sandwich problem for 1-join composition is NP-complete
• On decision and optimization (\(k\),\(l\))-graph sandwich problems
• Improved lower bounds for graph embedding problems
• An improved derandomized approximation algorithm for the max-controlled set problem
• The pair completion algorithm for the homogeneous set sandwich problem
• The sandwich problem for cutsets: clique cutset, \(k\)-star cutset
• The homogeneous set sandwich problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1293876)