Testing convexity properties of tree colorings

DOI10.1007/s00453-009-9368-2zbMath1217.05088OpenAlexW2041664513MaRDI QIDQ547293

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 algorithmsproperty testingphylogenetic treesconvex coloringsublinear algorithmsmassively parameterized

Mathematics Subject Classification ID

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

Related Items (1)

TESTING FOR FORBIDDEN POSETS IN ORDERED ROOTED FORESTS

Cites Work

• Self-testing/correcting with applications to numerical problems
• Regular Languages are Testable with a Constant Number of Queries
• Testing Membership in Languages that Have Small Width Branching Programs
• Property testing and its connection to learning and approximation
• Fast Algorithms for Finding Nearest Common Ancestors
• On the Query Complexity of Testing Orientations for Being Eulerian
• Monotonicity testing over general poset domains
• Testing st-Connectivity
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Testing the diameter of graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Algorithms and Data Structures
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Property testing in bounded degree graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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