FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:     | 1 |   ...   | 13 | 14 || 16 |

«Gefördert durch die Deutsche Forschungsgemeinschaft im Rahmen des Graduiertenkollegs ’Methods for Discrete Structures’ (GRK 1408) Präsident der ...»

-- [ Page 15 ] --

[AS06] Alon, Noga; Shapira, Asaf: A characterization of easily testable induced subgraphs. In: Combinatorics, Probability and Computing, volume 15(6):pp.

791–805, 2006. doi:10.1017/S0963548306007759.

Bibliography [BD07] Bläser, Markus; Dell, Holger: Complexity of the cover polynomial. In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP 2007, volume 4596 of Lecture Notes in Computer Science, pp. 801–812. Springer, 2007. doi:10.1007/978-3-540-73420-8_69.

[BDFH09] Bodlaender, Hans L.; Downey, Rodney G.; Fellows, Michael R.; Hermelin, Danny: On problems without polynomial kernels. In: Journal of Computer

and System Sciences, volume 75(8):pp. 423–434, 2009. ISSN 0022-0000. doi:


[Beh46] Behrend, Felix A.: On sets of integers which contain no three terms in arithmetic progression. In: Proceedings of the National Academy of Sciences, USA, volume 32(12):pp. 331–332, 1946. doi:10.1073/pnas.32.12.331.

[Ber84] Berkowitz, Stuart J.: On computing the determinant in small parallel time using a small number of processors. In: Information Processing Letters, volume 18(3):pp. 147–150, 1984. doi:10.1016/0020-0190(84)90018-8.

[BG93] Buss, Jonathan F.; Goldsmith, Judy: Nondeterminism within P. In:

SIAM Journal on Computing, volume 22(3):pp. 560–572, 1993. doi:10.1007/ BFb0020811.

[BH08a] Björklund, Andreas; Husfeldt, Thore: Exact algorithms for exact satisfiability and number of perfect matchings. In: Algorithmica, volume 52(2):pp.

226–249, 2008. doi:10.1007/s00453-007-9149-8.

[BH08b] Buhrman, Harry; Hitchcock, John M.: NP-hard sets are exponentially dense unless NP is contained in coNP/poly. In: Proceedings of the 23rd IEEE Conference on Computational Complexity, CCC 2008, pp. 1–7. IEEE Computer Society, 2008. doi:10.1109/CCC.2008.21.

[BHKK08] Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko: Computing the Tutte polynomial in vertex-exponential time. In: Proceedings of the 47th annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, pp. 677–686. 2008. doi:10.1109/FOCS.2008.40.

[Bry82] Brylawski, Thomas: The Tutte polynomial, Matroid theory and its applications. In: Centro Internazionale Matematico Estivo, pp. 125–275, 1982.

[BTY09] Bodlaender, Hans L.; Thomassé, Stéphan; Yeo, Anders: Kernel bounds for disjoint cycles and disjoint paths. In: Proceedings of the 17th Annual European Symposium on Algorithms, ESA 2009, volume 5757 of

Lecture Notes in Computer Science, pp. 635–646. Springer, 2009. doi:


[CFL83] Chandra, Ashok K.; Furst, Merrick L.; Lipton, Richard J.: Multi-party protocols. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing, STOC 1983, pp. 94–99. ACM, 1983. doi:10.1145/800061.808737.

–  –  –

[CFM07] Chen, Yijia; Flum, Jörg; Müller, Moritz: Lower bounds for kernelizations. In: Electronic Colloquium on Computational Complexity (ECCC), volume 14(137), 2007. URL http://eccc.hpi-web.de/eccc-reports/2007/ TR07-137/index.html.

[CIKP03] Calabro, Chris; Impagliazzo, Russell; Kabanets, Valentine; Paturi, Ramamohan: The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs.

In: Proceedings of the 18th IEEE Conference on Computational Complexity, CCC 2003, p. 135. IEEE Computer Society, 2003. ISBN 0769518796. ISSN 1093-0159. doi:10.1109/CCC.2003.1214416.

[CIP06] Calabro, Chris; Impagliazzo, Russell; Paturi, Ramamohan: A duality between clause width and clause density for SAT. In: Proceedings of the 21st IEEE Conference on Computational Complexity, CCC 2006, pp. 252–260.

IEEE Computer Society, 2006. doi:10.1109/CCC.2006.6.

[Coo71] Cook, Stephen A.: The complexity of theorem-proving procedures. In: Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, STOC 1971, pp. 151–158. ACM, 1971. doi:10.1145/800157.805047.

[CW90] Coppersmith, Don; Winograd, Shmuel: Matrix multiplication via arithmetic progressions. In: Journal of Symbolic Computation, volume 9(3):pp. 251– 280, 1990. doi:10.1016/S0747-7171(08)80013-2.

[DF99] Downey, Rodney G.; Fellows, Michael R.: Parameterized complexity.

Springer New York, 1999.

[DHW10] Dell, Holger; Husfeldt, Thore; Wahlén, Martin: Exponential time complexity of the permanent and the Tutte polynomial. In: Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP 2010, volume 6198 of Lecture Notes in Computer Science, pp. 426–

437. Springer, 2010. doi:10.1007/978-3-642-14165-2_37.

[Din07] Dinur, Irit: The PCP theorem by gap amplification. In: Journal of the ACM, volume 54(3):p. 12, 2007. doi:10.1145/1236457.1236459.

[DJP+ 94] Dahlhaus, Elias; Johnson, David S.; Papadimitriou, Christos H.; Seymour,

Paul D.; Yannakakis, Mihalis: The complexity of multiterminal cuts. In:

SIAM Journal on Computing, volume 23(4):pp. 864–894, 1994. doi:10.1137/ S0097539792225297.

[DLS09] Dom, Michael; Lokshtanov, Daniel; Saurabh, Saket: Incompressibility through colors and IDs. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP 2009, volume 5555 of Lecture Notes in Computer Science, pp. 378–389. Springer, 2009.



[DvM10] Dell, Holger; van Melkebeek, Dieter: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: Proceedings of the 42th Annual ACM Symposium on Theory of Computing, STOC 2010, pp. 251–260. ACM, 2010. doi:10.1145/1806689.1806725.

[Elk10] Elkin, Michael: An improved construction of progression-free sets. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pp. 886–905. SIAM, 2010.

[ER60] Erdős, Paul; Rado, Richard: Intersection theorems for systems of sets. In:

Journal of the London Mathematical Society, volume 35:pp. 85–90, 1960.


[FB99] Friedgut, Ehud; Bourgain, Jean: Sharp thresholds of graph properties, and the k-SAT problem. In: Journal of the American Mathematical Society, volume 12(4):pp. 1017–1054, 1999. doi:10.1090/S0894-0347-99-00305-7.

[FFL+ 09] Fernau, Henning; Fomin, Fedor V.; Lokshtanov, Daniel; Raible, Daniel;

Saurabh, Saket; Villanger, Yngve: Kernel(s) for problems with no kernel: On out-trees with many leaves. In: Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, volume 09001 of Dagstuhl Seminar Proceedings, pp. 421–432. 2009.


[FG06] Flum, Jörg; Grohe, Martin: Parameterized Complexity Theory. Springer, 2006.

[FGMN09] Fellows, Michael R.; Guo, Jiong; Moser, Hannes; Niedermeier, Rolf: A generalization of Nemhauser and Trotter’s local optimization theorem. In: Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, volume 09001 of Dagstuhl Seminar Proceedings, pp. 409–420. 2009. doi:10.4230/LIPIcs.STACS.2009.1820.

[FHR+ 04] Fellows, Michael R.; Heggernes, Pinar; Rosamond, Frances A.; Sloper, Christian; Telle, Jan Arne: Finding k disjoint triangles in an arbitrary graph. In:

Proceedings of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2004), volume 3353 of Lecture Notes in Computer Science, pp. 235–244. Springer, 2004. doi:10.1007/b104584.

[FK72] Fortuin, Cees M.; Kasteleyn, Pieter W.: On the random-cluster model: I.

Introduction and relation to other models. In: Physica, volume 57(4):pp.

536–564, 1972. ISSN 0031-8914. doi:10.1016/0031-8914(72)90045-6.

[FKN+ 08] Fellows, Michael R.; Knauer, Christian; Nishimura, Naomi; Ragde, Prabhakar; Rosamond, Frances A.; Stege, Ulrike; Thilikos, Dimitrios M.; Whitesides, Sue: Faster fixed-parameter tractable algorithms for matching an packing problems. In: Algorithmica, volume 52:pp. 167–176, 2008. ISSN 0178-4617. doi:10.1007/s00453-007-9146-y.

–  –  –

[FR09] Fernau, Henning; Raible, Daniel: A parameterized perspective on packing paths of length two. In: Journal of Combinatorial Optimization, volume 18(4):pp. 319–341, 2009. doi:10.1007/s10878-009-9230-0.

[FS08] Fortnow, Lance; Santhanam, Rahul: Infeasibility of instance compression and succinct PCPs for NP. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC 2008, pp. 133–142. ACM, 2008.


[GGR98] Goldreich, Oded; Goldwasser, Shafi; Ron, Dana: Property testing and its connection to learning and approximation. In: Journal of the ACM, volume 45(4):pp. 653–750, 1998. doi:10.1145/285055.285060.

[GHN06] Giménez, Omer; Hliněný, Petr; Noy, Marc: Computing the Tutte polynomial on graphs of bounded clique-width. In: SIAM Journal on Discrete Mathematics, volume 20:pp. 932–946, 2006. doi:10.1007/11604686_6.

[GJ07] Goldberg, Leslie Ann; Jerrum, Mark: The complexity of ferromagnetic Ising with local fields. In: Combinatorics, Probability and Computing, volume 16(1):pp. 43–61, 2007. doi:10.1017/S096354830600767X.

[GJ08] Goldberg, Leslie Ann; Jerrum, Mark: Inapproximability of the Tutte polynomial. In: Information and Computation, volume 206(7):pp. 908–929, 2008.


[GN07] Guo, Jiong; Niedermeier, Rolf: Invitation to data reduction and problem kernelization. In: SIGACT News, volume 38(1):pp. 31–45, 2007. ISSN 0163doi:10.1145/1233481.1233493.

[Gol08] Goldreich, Oded: Computational complexity: a conceptual perspective. ACM New York, NY, USA, 2008.

[GR01] Godsil, Chris; Royle, Gordon: Algebraic Graph Theory. Graduate Texts in Mathematics. Springer, April 2001. ISBN 0387952209.

[GW08] Green, Ben; Wolf, Julia: A note on Elkin’s improvement of Behrend’s construction, 2008. arXiv:0810.0732.

[HHN+ 95] Hemaspaandra, Lane A.; Hoene, Albrecht; Naik, Ashish V.; Ogihara, Mitsunori; Selman, Alan L.; Thierauf, Thomas; Wang, Jie: Nondeterministically selective sets. In: International Journal of Foundations of Computer Science, volume 6(4):pp. 403–416, 1995. doi:10.1142/S0129054195000214.

[HN06] Harnik, Danny; Naor, Moni: On the compressibility of NP instances and cryptographic applications. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006, pp. 719–728. 2006.


Bibliography [Hof10] Hoffmann, Christian: Exponential time complexity of weighted counting of independent sets. In: Proceedings of the 5th International Symposium on Parameterized and Exact Complexity, IPEC 2010, volume 6478

of Lecture Notes in Computer Science, pp. 180–191. Springer, 2010. doi:


[HT10] Husfeldt, Thore; Taslaman, Nina: The exponential time complexity of computing the probability that a graph is connected. In: Proceedings of the 5th International Symposium on Parameterized and Exact Complexity, IPEC 2010, volume 6478 of Lecture Notes in Computer Science, pp. 192–203.

Springer, 2010. doi:10.1007/978-3-642-17493-3_19.

[HW03] Håstad, Johan; Wigderson, Avi: Simple analysis of graph tests for linearity and PCP. In: Random Structures and Algorithms, volume 22(2):pp. 139–160,

2003. doi:10.1002/rsa.10068.

[IPZ01] Impagliazzo, Russell; Paturi, Ramamohan; Zane, Francis: Which problems have strongly exponential complexity? In: Journal of Computer and System Sciences, volume 63(4):pp. 512–530, 2001. ISSN 0022-0000. doi:10.1006/jcss.


[Ist00] Istrail, Sorin: Statistical mechanics, three-dimensionality and NP-completeness. I. Universality of intractability for the partition function of the Ising model across non-planar lattices. In: Proceedings of the 32nd annual ACM Symposium on Theory of Computing, STOC 2000, pp. 87–96. ACM, 2000.


[JS82] Jerrum, Mark; Snir, Marc: Some exact complexity results for straight-line computations over semirings. In: Journal of the ACM, volume 29(3):pp.

874–897, 1982. doi:10.1145/322326.322341.

[JS93] Jerrum, Mark; Sinclair, Alistair: Polynomial-time approximation algorithms for the Ising model. In: SIAM Journal on Computing, volume 22(5):pp.

1087–1116, 1993. doi:10.1137/0222066.

[JVW90] Jaeger, François; Vertigan, Dirk L.; Welsh, Dominic J.A.: On the computational complexity of the Jones and Tutte polynomials. In: Mathematical proceedings of the Cambridge Philosophical Society, volume 108(1):pp. 35–53,

1990. doi:10.1017/S0305004100068936.

[Kar72] Karp, Richard M.: Reducibility among combinatorial problems. In: Complexity of computer computations, volume 43:pp. 85–103, 1972.

[KD79] Krishnamoorthy, Mukkai S.; Deo, Narsingh: Node-deletion NP-complete problems. In: SIAM Journal on Computing, volume 8(4):pp. 619–625, 1979.


–  –  –

[KH78] Kirkpatrick, David G.; Hell, Pavol: On the completeness of a generalized matching problem. In: Proceedings of the 10th annual ACM Symposium on Theory of Computing, STOC 1978, pp. 240–245. ACM, 1978. doi:10.1145/ 800133.804353.

[KMW10] Kratsch, Stefan; Marx, Dániel; Wahlström, Magnus: Parameterized complexity and kernelizability of max ones and exact ones problems. In: Proceedings of the 35th International Symposium on Mathematical Foundations of Computer Science, MFCS 2010, pp. 489–500. 2010. doi:10.1007/ 978-3-642-15155-2_43.

[Ko83] Ko, Ker-I: On self-reducibility and weak P-selectivity. In: Journal of

Computer and System Sciences, volume 26(2):pp. 209–221, 1983. doi:


[Koi09] Koivisto, Mikko: Partitioning into sets of bounded cardinality. In: Proceedings of the 4th International Workshop on Parameterized and Exact Complexity, IWPEC 2009, volume 5917 of Lecture Notes in Computer Science, pp. 258–263. Springer, 2009. doi:10.1007/978-3-642-11269-0_21.

[Kot00] Kotlov, Andrei: Short proof of the Gallai-Edmonds structure theorem, 2000.


[Kut07] Kutzkov, Konstantin: New upper bound for the #3-SAT problem. In: Information Processing Letters, volume 105(1):pp. 1–5, 2007. ISSN 0020-0190.


Pages:     | 1 |   ...   | 13 | 14 || 16 |

Similar works:

«DISSERTATION Titel der Dissertation „Elemente ritueller Handlungen in den Elija-Elischa-Erzählungen“ Untersuchungen zur literarischen Umsetzung ritueller Handlungselemente im Vergleich zur mesopotamischen keilschriftlichen Tradition. Verfasser Mag. theol. Gerhard Karner angestrebter akademischer Grad Doktor der Theologie (Dr. theol.) Wien, Dezember 2009 Studienkennzahl lt. Studienblatt: A 082 041 Dissertationsgebiet lt. Studienblatt: Evangelische Fachtheologie Betreuerin / Betreuer: O....»

«Indian Rhino Vision 2020 Population Modeling Workshop FINAL REPORT FROM THE WORKSHOP HELD 4-5 NOVEMBER 2014 Guwahati, Assam, India Edited by Ellis, S., Miller, P.S., Agarwalla, R.P., M.K. Yadava, Ghosh, S., Sivakumar, P., Smarajit Ojah, Bhattacharya, U., Singh, V.K., Sharma, A., and Talukdar, B.K. Compiled by the Workshop Participants Indian Rhino Vision 2020 Population Modeling Workshop, November 2014 1 FINAL REPORT Reference: Ellis, S., Miller, P.S., Agarwalla, R.P., Yadava, M.K., Ghosh, S.,...»

«gen istun len lerle tiona chü rna S inte im leich Verg ür nf zeptio on hmenk issen a neue R von W Eine g rfassun ten die E igkei h und Fä OECD PROGRAMME F O R I N T E R N AT I O N A L STUDENT ASSESSMENT SCHÜLERLEISTUNGEN IM INTERNATIONALEN VERGLEICH Eine neue Rahmenkonzeption für die Erfassung von Wissen und Fähigkeiten Herausgeber der deutschen Fassung: Deutsches PISA-Konsortium Herausgeber der englischen und französischen Originalfassung: OECD OECD PROGRAMME FOR INTERNATIONAL STUDENT...»

«‘Every real moment’ in photographic work by Andy Warhol Sara Rundgren Yazdani Master Thesis in Media Studies Institution of Media and Communication University of Oslo Spring 2012 © Sara Rundgren Yazdani ’Every Real Moment’ in Photographic Work by Andy Warhol Sara Rundgren Yazdani http://www.duo.uio.no/ Trykk: Reprosentralen, Universitetet i Oslo     II     What I liked was chunks of time all together, every real moment. Andy Warhol (and Hackett 1980: 138)     III         IV...»

«Lärmaktionsplanung Königs Wusterhausen 19. September 2008 Berlin Hamburg Novalisstraße 10 Altonaer Poststraße 13b D-10115 Berlin-Mitte D-22767 Hamburg-Altona Tel: 030 / 322 95 25 30 Tel: 040 / 38 99 94 50 Fax: 030 / 322 95 25 55 Fax: 040 / 38 99 94 55 email: berlin@LKargus.de email: hamburg@LKargus.de www.LKargus.de www.LKargus.de Lärmaktionsplanung Königs Wusterhausen Bearbeitung: Dr.-Ing. Eckhart Heinrichs Dipl.-Ing. Sibylle Rath Dipl.-Ing. Susan Schreiber Auftraggeber: Stadt Königs...»

«GovTrip Frequently Asked Questions U.S. Fish and Wildlife Service GovTrip Frequently Asked Questions General eTravel Questions 1. What is eTravel? 2. How was eTravel implemented? 3. Now that eTravel is implemented, are FWS employees allowed to bypass the GovTrip system to book government travel? 4. Can I still submit a paper Travel Voucher (SF-1012) for TDY travel? 5. Does the National Business Center (NBC) still review Travel Vouchers before payment is submitted through the Federal Financial...»

«Office for Bombing Prevention Counter-IED Resources Guide April 2014 Counter-IED Resources Guide OVERVIEW —  Vision & Mission: The Office for Bombing Prevention was born of terrorism events such as Lockerbie, Oklahoma City, September 11th, Madrid, and London. Our service is rooted in the belief that bombings continue to threaten the security of our communities, critical infrastructure, and nation. We believe that Americans and people everywhere should live free from fear of malicious use...»

«DRED SCOTT REVISITED HARRY V. JAFFA* I. It has been many years since I first wrote that the American Revolution was, at once, an event in time and an idea out of time.1 Lincoln meant no less when he wrote that Jefferson enshrined in the Declaration of Independence “an Abstract truth, applicable to all men and all times.”2 It was a commonplace among the Founders (and Lincoln) that the American experiment in self-government was not for Americans alone, but for all mankind.3 This was not...»

«AMC MUSEUM FOUNDATIO N, INC. P.O. BOX 020 50 DOVER AFB, DE 19902 -2050 Hangar Digest V OLUME 2, I SSUE 3 J ULY 2002 I N S ID E T H IS IS S U E : From the Director 2 From The Editor: Curator’s Corner 2 Meet the Volunteer 6 I would like to welcome all the Artifact Facts 6 new ―Friends‖ of the Air Mobility Around the Bases 8 Command Museum and thank all others for their continued support. Name the Plane 9 As most of you are aware, each Building 1301 11 September, the AMC Museum’s...»

«ICOTS-7, 2006: Kong and Harradine CENSUSATSCHOOL IN AUSTRALIA Soo Kong Australian Bureau of Statistics, Australia Anthony Harradine Prince Alfred College, Australia soo.kong@abs.gov.au The CensusAtSchool project is an initiative undertaken by the Australian Bureau of Statistics (ABS) aimed at meeting two key objectives: (1) the development of statistical literacy amongst 10 17 year old students across Australia; (2) to promote the 2006 Census of Population and Housing. The paper highlights the...»

«Christelle Wauthier Department of Geosciences and +1-814-863-6649 (work) Institute for CyberScience cuw25@psu.edu The Pennsylvania State University http://www.geosc.psu.edu/academicfaculty/wauthier-christelle University Park, PA 16802-2714 Current Appointment 2014 – present Assistant Professor Department of Geosciences & Institute for CyberScience, Pennsylvania State University, University Park, PA 16802, USA Education 2007 – 2011 PhD in engineering sciences (advisor: Prof. Eric Pirard)...»

«Change Your Brain, Change Your Life The Breakthrough Program for Conquering Anxiety, Depression, Obsessiveness, Anger, and Impulsiveness Daniel G Amen Three Rivers Press New York Looking Into Anxiety and Fear: The Basal Ganglia Functions of the Basal Ganglia System integrates feeling and movement shifts and smoothes fine motor behavior suppresses unwanted motor behaviors sets the body's idle speed or anxiety level enhances motivation mediates pleasure/ecstasy. The basal ganglia are a set of...»

<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.