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)

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

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)

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