Workplace-Based Assessments During Training
Workplace-based assessments play a crucial role in evaluating trainees' competency and progress in their day-to-day work. Various assessment tools are utilized, such as direct observation of practical skills, case-based discussions, and multi-source feedback, all linked to the curriculum. Documentation of assessments is essential for recording progress and supporting the overall training process for pathology trainees.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
U N I V E R S I T Y O F B E R G E N Algorithms Research Group A Near-Optimal Planarization Algorithm Bart M. P. Jansen Daniel Lokshtanov University of Bergen, Norway Saket Saurabh Institute of Mathematical Sciences, India uib.no January 7th 2014, SODA, Portland
Algorithms Research Group Problem setting Generalization of the PLANARITY TESTING problem k-VERTEX PLANARIZATION In: An undirected graph G, integer k Q: Can k vertices be deleted from G to get a planar graph? Vertex set S such that G S is planar, is an apex set Planarization is NP-complete [Lewis & Yanakkakis] Applications: Visualization Approximation schemes for graph problems on nearly- planar graphs 2 uib.no
Algorithms Research Group Previous planarization algorithms Robertson & Seymour (1980 s) For every fixed k, there is an O O(n3)-time algorithm Non-constructive (Graph-minors theorem) Involves astronomical constants Marx & Schlotter (2007, 2012) Constructive 2??(?3) ?2-time algorithm Based on iterative compression, treewidth reduction & dynamic programming Kawarabayashi (2009) Constructive 2? (?3) ?-time algorithm Techniques from graph minors project instead of iterative compression Chekuri & Sidiropoulos (2013) Polynomial-time poly(OPT, log n) approximation on bounded-degree graphs 3 uib.no
Algorithms Research Group Our contribution Algorithm with runtime 2?(? log ?) ? Using new treewidth-DP with runtime 2?(? log ?) ? Based on elementary techniques: Breadth-first search Planarity testing Decomposition into 3-connected components Tree decompositions of k-outerplanar graphs Our algorithm is near-optimal Linear dependence on n cannot be improved Assuming the Exponential-Time Hypothesis, the problem cannot be solved in 2?(?)??(1)time 4 uib.no
Algorithms Research Group Preliminaries Radial distance between u and v in a plane graph: Length of a shortest u-v path when hopping between vertices incident on a common face in a single step Radial c-ball around v: Vertices at radial distance c from v Induces a subgraph of treewidth O O(c) Outerplanarity layers of a plane graph G: Partition V(G) by iteratively removing vertices on the outer face 5 uib.no
Algorithms Research Group Algorithm outline I. Find approximate apex set Apex set of size O O(k) II. Reduce treewidth to O O(k) Irrelevant vertices inside planar walls III. Dynamic programming On tree decomposition of width O O(k) 6 uib.no
Algorithms Research Group I. Finding an approximate apex set Marx & Schlotter used iterative compression in (n2) time Our linear-time strategy: 1. Preprocessing step to reduce number of false twins 2. Greedily find a maximal matching M If there is a k-apex set, |M| ? ? 2? 3. Contract edges in M, recurse on G/M to get apex set SM 4. Let S1 V(G) contain SMand its matching partners (G S1)/M is planar Output S1 (approximate apex set in G-S1) Reduces to approximation on matching-contractible graphs 7 uib.no
Algorithms Research Group Matching-contractible graphs A matching-contractible graph H with embedded H/M is locally planar if: for each vertex v of H/M, the subgraph of H/M induced by the 3-ball around v remains planar when decontracting M Theorem. If a matching-contractible graph is locally planar, We prove: If a matching-contractible graph is locally planar, it is planar then it is (globally) planar Allows us to reduce the planarization task on H to (decontracted) bounded-radius subgraphs of H/M These have bounded treewidth and can be analyzed by our treewidth DP Yields FPT-approximation in matching-contractible graphs With the previous step: approximate apex set in linear time 8 uib.no
Algorithms Research Group II. Reducing treewidth Given an apex set S of size O O(k), reduce the treewidth without changing the answer Sufficient to reduce treewidth of planar graph G-S Previous algorithms use two steps: Delete apices in S that have to be part of every solution Delete vertices in planar subgraphs surrounded by (k) concentric cycles Conceptually simple, but treewidth remains (? ?) 9 uib.no
Algorithms Research Group Linear-time treewidth reduction to O O(k) How to decrease width to O O(k)? Previous irrelevant-vertex arguments triggered for vertices surrounded by (k) concentric cycles Need (k) to ensure that after k deletions, some isolating cycle remains Solution: Introduce annotated version of the problem where some vertices are forbidden to be deleted by a solution O O(1) undeletable cycles make a vertex irrelevant Annotation ensures the cycles survive when deleting a solution Proceedings paper gives intuitive description of the process 10 uib.no
Algorithms Research Group Guessing undeletable regions Baker-like layering approach to guess parts where no deletions are needed Usually: partition into k+1 groups to ensure there is 1 group that avoids a size-k solution But: solution does not live in the planar graph Neighborhood of the solution lives in the planar graph Can be arbitrarily much larger than the size-k solution Theorem: If there is a solution disjoint from the approximate solution, then its neighborhood in a 3-connected component of the planar graph can be covered by O O(k) balls of constant radius Branch to guess how a solution intersects the approximate apex set Cover the neighborhood of the remaining apices by c-balls Avoid these balls in the layering scheme Afterwards treewidth reduction can be done in linear-time using BFS 11 uib.no
Algorithms Research Group III. Dynamic programming Previous algorithms for VERTEX PLANARIZATION on graphs of bounded treewidth were doubly-exponential in treewidth w States for a bag X based on partial models of Kuratowski minors after deleting some S X Requires 22? states per bag We give an algorithm with running time 2?(? log ?) ? States are based on possible embeddings of the graph Similar approach as Kawarabayashi, Mohar & Reed for computing genus of bounded-treewidth graphs Unlikely that 2?(? log ?) ? is possible [Marcin Pilipczuk] 12 uib.no
Algorithms Research Group Conclusion Near-optimal algorithm for k-VERTEX PLANARIZATION using elementary techniques FPT-approximation in matching-contractible graphs Treewidth reduction to O O(k) using undeletable vertices Dynamic program in 2?(? log ?) ? time 2?(?) ? algorithm? (avoid treewidth?) Open problems Polynomial-size problem kernel? Poly(OPT) approximation in general graphs? Linear-time algorithm for vertex-deletion to get a toroidal graph? H-minor-free graph? Planarization by edge deletion and contraction? 13 uib.no
Thank you! Algorithms Research Group
