Testing convexity properties of tree colorings

DOI10.1007/S00453-009-9368-2zbMATH Open1217.05088OpenAlexW2041664513MaRDI QIDQ547293FDOQ547293

Eldar Fischer, Orly Yahalom

Publication date: 1 July 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9368-2

Recommendations

• Testing Convexity Properties of Tree Colorings
• Algorithms and Data Structures
• Convex recolorings of strings and trees: Definitions, hardness results and algorithms
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Efficient approximation of convex recolorings

zbMATH Keywords

graph algorithmsconvex coloringproperty testingsublinear algorithmsphylogenetic treesmassively parameterized

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Property testing and its connection to learning and approximation
• Algorithms and Data Structures
• Property testing in bounded degree graphs
• Self-testing/correcting with applications to numerical problems
• On the Query Complexity of Testing Orientations for Being Eulerian
• Monotonicity testing over general poset domains
• Testing st-Connectivity
• Title not available (Why is that?)
• Robust Characterizations of Polynomials with Applications to Program Testing
• Title not available (Why is that?)
• Fast Algorithms for Finding Nearest Common Ancestors
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Regular languages are testable with a constant number of queries
• Testing Membership in Languages that Have Small Width Branching Programs
• Title not available (Why is that?)
• Testing the diameter of graphs
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

Cited In (1)

• TESTING FOR FORBIDDEN POSETS IN ORDERED ROOTED FORESTS

This page was built for publication: Testing convexity properties of tree colorings

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