LEADER 06703nam 22008415 450 001 996465317803316 005 20200701015217.0 010 $a1-280-30821-4 010 $a9786610308217 010 $a3-540-28639-X 024 7 $a10.1007/b100584 035 $a(CKB)1000000000212559 035 $a(DE-He213)978-3-540-28639-4 035 $a(SSID)ssj0000217974 035 $a(PQKBManifestationID)11173339 035 $a(PQKBTitleCode)TC0000217974 035 $a(PQKBWorkID)10214667 035 $a(PQKB)10255007 035 $a(MiAaPQ)EBC3088602 035 $a(PPN)155192477 035 $a(EXLCZ)991000000000212559 100 $a20121227d2004 u| 0 101 0 $aeng 135 $aurnn#008mamaa 181 $ctxt$2rdacontent 182 $cc$2rdamedia 183 $acr$2rdacarrier 200 10$aParameterized and Exact Computation$b[electronic resource] $eFirst International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004, Proceedings /$fedited by Frank Dehne, Rod Downey, Michael Fellows 205 $a1st ed. 2004. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2004. 215 $a1 online resource (X, 298 p.) 225 1 $aLecture Notes in Computer Science,$x0302-9743 ;$v3162 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a3-540-23071-8 320 $aIncludes bibliographical references at the end of each chapters and index. 327 $aParameterized Enumeration, Transversals, and Imperfect Phylogeny Reconstruction -- Online Problems, Pathwidth, and Persistence -- Chordless Paths Through Three Vertices -- Computing Small Search Numbers in Linear Time -- Bounded Fixed-Parameter Tractability: The Case 2poly( k) -- Refined Memorisation for Vertex Cover -- Parameterized Graph Separation Problems -- Parameterized Coloring Problems on Chordal Graphs -- On Decidability of MSO Theories of Representable Matroids -- On Miniaturized Problems in Parameterized Complexity Theory -- Smaller Kernels for Hitting Set Problems of Constant Arity -- Packing Edge Disjoint Triangles: A Parameterized View -- Looking at the Stars -- Moving Policies in Cyclic Assembly-Line Scheduling -- A Structural View on Parameterizing Problems: Distance from Triviality -- Perfect Path Phylogeny Haplotyping with Missing Data Is Fixed-Parameter Tractable -- Simplifying the Weft Hierarchy -- The Minimum Weight Triangulation Problem with Few Inner Points -- A Direct Algorithm for the Parameterized Face Cover Problem -- On Finding Short Resolution Refutations and Small Unsatisfiable Subsets -- Parameterized Algorithms for Feedback Vertex Set -- Automated Proofs of Upper Bounds on the Running Time of Splitting Algorithms -- Improved Parameterized Algorithms for Feedback Set Problems in Weighted Tournaments -- Greedy Localization, Iterative Compression, and Modeled Crown Reductions: New FPT Techniques, an Improved Algorithm for Set Splitting, and a Novel 2k Kernelization for Vertex Cover -- Space and Time Complexity of Exact Algorithms: Some Open Problems -- Practical FPT Implementations and Applications. 330 $aThecentralchallengeoftheoreticalcomputerscienceistodeploymathematicsin waysthatservethecreationofusefulalgorithms. Inrecentyearstherehasbeena growinginterest in the two-dimensionalframework of parameterizedcomplexity, where, in addition to the overall input size, one also considers a parameter,with a focus on how these two dimensions interact in problem complexity. This book presents the proceedings of the 1st InternationalWorkshopon - rameterized and Exact Computation (IWPEC 2004,http://www. iwpec. org), which took place in Bergen, Norway, on September 14?16, 2004. The workshop was organized as part of ALGO 2004. There were seven previous workshops on the theory and applications of parameterized complexity. The ?rst was - ganized at the Institute for the Mathematical Sciences in Chennai, India, in September, 2000. The second was held at Dagstuhl Castle, Germany, in July, 2001. In December, 2002, a workshop on parameterized complexity was held in conjunction with the FST-TCS meeting in Kanpur, India. A second Dagstuhl workshop on parameterized complexity was held in July, 2003. Another wo- shoponthesubjectwasheldinOttawa,Canada,inAugust,2003,inconjunction with the WADS 2003 meeting. There have also been two Barbados workshops on applications of parameterized complexity. In response to the IWPEC 2004 call for papers, 47 papers were submitted, and from these the programcommittee selected 25 for presentation at the wo- shop. Inaddition,invitedlectureswereacceptedbythedistinguishedresearchers Michael Langston and Gerhard Woeginger. 410 0$aLecture Notes in Computer Science,$x0302-9743 ;$v3162 606 $aAlgorithms 606 $aProbabilities 606 $aApplication software 606 $aComputers 606 $aData structures (Computer science) 606 $aComputer science?Mathematics 606 $aAlgorithm Analysis and Problem Complexity$3https://scigraph.springernature.com/ontologies/product-market-codes/I16021 606 $aProbability Theory and Stochastic Processes$3https://scigraph.springernature.com/ontologies/product-market-codes/M27004 606 $aComputer Applications$3https://scigraph.springernature.com/ontologies/product-market-codes/I23001 606 $aComputation by Abstract Devices$3https://scigraph.springernature.com/ontologies/product-market-codes/I16013 606 $aData Structures$3https://scigraph.springernature.com/ontologies/product-market-codes/I15017 606 $aDiscrete Mathematics in Computer Science$3https://scigraph.springernature.com/ontologies/product-market-codes/I17028 615 0$aAlgorithms. 615 0$aProbabilities. 615 0$aApplication software. 615 0$aComputers. 615 0$aData structures (Computer science). 615 0$aComputer science?Mathematics. 615 14$aAlgorithm Analysis and Problem Complexity. 615 24$aProbability Theory and Stochastic Processes. 615 24$aComputer Applications. 615 24$aComputation by Abstract Devices. 615 24$aData Structures. 615 24$aDiscrete Mathematics in Computer Science. 676 $a519.5/44 702 $aDehne$b Frank$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aDowney$b Rod$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aFellows$b Michael$4edt$4http://id.loc.gov/vocabulary/relators/edt 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a996465317803316 996 $aParameterized and Exact Computation$9772030 997 $aUNISA