Testing for forbidden posets in ordered rooted forests

DOI10.1142/S0129054112500219MaRDI QIDQ4923287zbMATH OpenOpenAlexFDO

Authors Orly Yahalom

Publication date 6 June 2013

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054112500219

zbMATH Keywords

forbidden posetsmassively parameterizedordered treesproperty testingvertex coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Combinatorics of partially ordered sets (06A07) Randomized algorithms (68W20)

Recommendations

• Testing for forbidden order patterns in an array
• Testing for forbidden order patterns in an array
• Testing of matrix-poset properties
• Testing of matrix properties
• Improved bounds for testing forbidden order patterns

Cites work

• Algorithmic and analysis techniques in property testing
• Information theory in property testing and monotonicity testing in higher dimension
• Proof verification and the hardness of approximation problems
• Property testing and its connection to learning and approximation
• Property testing in bounded degree graphs
• Property testing of massively parametrized problems -- a survey
• Property testing. Current research and surveys
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems
• Sound 3-query PCPPs are long
• Testing convexity properties of tree colorings

Cited in

(2)

• Testing of matrix-poset properties
• Testing for forbidden order patterns in an array

This page was built for publication: Testing for forbidden posets in ordered rooted forests

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