Testing convexity properties of tree colorings

DOI10.1007/S00453-009-9368-2MaRDI QIDQ547293zbMATH OpenOpenAlexFDO

Authors 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

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)

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

Cites work

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

Cited in

(2)

• Testing Convexity Properties of Tree Colorings
• 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)