liu.seSearch for publications in DiVA
Change search
Refine search result
1 - 12 of 12
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1. Engstrom, Robert
    et al.
    Färnqvist, Tommy
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Thapper, Johan
    University of Paris Est Marne La Vallee, France.
    An Approximability-related Parameter on Graphs - Properties and Applications2015In: DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, ISSN 1462-7264, Vol. 17, no 1, p. 33-66Article in journal (Refereed)
    Abstract [en]

    We introduce a binary parameter on optimisation problems called separation. The parameter is used to relate the approximation ratios of different optimisation problems; in other words, we can convert approximability (and non-approximability) result for one problem into (non)-approximability results for other problems. Our main application is the problem (weighted) maximum H-colourable subgraph (MAX H-COL), which is a restriction of the general maximum constraint satisfaction problem (MAX CSP) to a single, binary, and symmetric relation. Using known approximation ratios for MAX k-CUT, we obtain general asymptotic approximability results for MAX H-COL for an arbitrary graph H. For several classes of graphs, we provide near-optimal results under the unique games conjecture. We also investigate separation as a graph parameter. In this vein, we study its properties on circular complete graphs. Furthermore, we establish a close connection to work by Samal on cubical colourings of graphs. This connection shows that our parameter is closely related to a special type of chromatic number. We believe that this insight may turn out to be crucial for understanding the behaviour of the parameter, and in the longer term, for understanding the approximability of optimisation problems such as MAX H-COL.

  • 2.
    Engström, Robert
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Färnqvist, Tommy
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Thapper, Johan
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Properties of an Approximability-related Parameter on Circular Complete Graphs2009In: Electronic Notes in Discrete Mathematics, ISSN 1571-0653, E-ISSN 1571-0653, Vol. 35, p. 115-120Article in journal (Refereed)
    Abstract [en]

    The instances of the Weighted Maximum H-Colourable Subgraph problem (Max H-Col) are edge-weighted graphs G and the objective is to find a subgraph of G that has maximal total edge weight, under the condition that the subgraph has a homomorphism to H; note that for H=Kk this problem is equivalent to Max k-cut. Färnqvist et al. have introduced a parameter on the space of graphs that allows close study of the approximability properties of Max H-Col. Here, we investigate the properties of this parameter on circular complete graphs Kp/q, where 2p/q3. The results are extended to K4-minor-free graphs. We also consider connections with Šámal's work on fractional covering by cuts: we address, and decide, two conjectures concerning cubical chromatic numbers.

  • 3.
    Färnqvist, Tommy
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Constraint Optimization Problems and Bounded Tree-width Revisited2012Conference paper (Other academic)
    Abstract [en]

    The valued constraint satisfaction problem (VCSP) is an optimization framework originating from artificial intelligence which generalizes the classical constraint satisfaction problem (CSP). In this paper, we are interested in structural properties that can make problems from the VCSP framework, as well as other CSP variants, solvable to optimality in polynomial time. So far, the largest structural class that is known to be polynomial-time solvable to optimality is the class of bounded hypertree width instances introduced by Gottlob et al. Here, larger classes of tractable instances are singled out by using dynamic programming and structural decompositions based on a hypergraph invariant proposed by Grohe and Marx. In the second part of the paper, we take a different view on our optimization problems; instead of considering fixed arbitrary values for some structural invariant of the (hyper)graph structure of the constraints, we consider the problems parameterized by the tree-width of primal, dual, and incidence graphs, combined with several other basic parameters such as domain size and arity. Such parameterizations of plain CSPs have been studied by Samer and Szeider. Here, we extend their framework to encompass our optimization problems, by coupling it with further non-trivial machinery and new reductions. By doing so, we are able to determine numerous combinations of the considered parameters that make our optimization problems admit fixed-parameter algorithms.

  • 4.
    Färnqvist, Tommy
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Counting Homomorphisms via Hypergraph-based Structural Restrictions2012Conference paper (Refereed)
    Abstract [en]

    The way in which the graph structure of the constraints influences the computational complexity of counting constraint satisfaction problems (#CSPs) is well understood for constraints of bounded arity. The situation is less clear if there is no bound on the arities. Here we initiate the systematic study of these problems and identify new classes of polynomial time solvable instances based on dynamic programming over tree decompositions, in a way generalizing well-known approaches to combinatorial optimization problems on bounded treewidth graphs, but basing the decompositions on various hypergraph width measures from the literature on plain CSPs.

  • 5.
    Färnqvist, Tommy
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Exploiting Structure in CSP-related Problems2013Doctoral thesis, monograph (Other academic)
    Abstract [en]

    In this thesis we investigate the computational complexity and approximability of computational problems from the constraint satisfaction framework. An instance of a constraint satisfaction problem (CSP) has three components; a set V of variables, a set D of domain values, and a set of constraints C. The constraints specify a set of variables and associated local conditions on the domain values allowed for each variable, and the objective of a CSP is to assign domain values to the variables, subject to these constraints.

    The first main part of the thesis is concerned with studying restrictions on the structure induced by the constraints on the variables for different computational problems related to the CSP. In particular, we examine how to exploit various graph, and hypergraph, acyclicity measures from the literature to find classes of relational structures for which our computational problems become efficiently solvable. Among the problems studied are, such where, in addition to the constraints of a CSP, lists of allowed domain values for each variable are specified (LHom). We also study variants of the CSP where the objective is changed to: counting the number of possible assignments of domain values to the variables given the constraints of a CSP (#CSP), minimising or maximising the cost of an assignment satisfying all constraints given various different ways of assigning costs to assignments (MinHom, Max Sol, and CSP), or maximising the number of satisfied constraints (Max CSP). In several cases, our investigations uncover the largest known (or possible) classes of relational structures for which our problems are efficiently solvable. Moreover, we take a different view on our optimisation problems MinHom and VCSP; instead of considering fixed arbitrary values for some (hyper)graph acyclicity measure associated with the underlying CSP, we consider the problems parameterised by such measures in combination with other basic parameters such as domain size and maximum arity of constraints. In this way, we identify numerous combinations of the considered parameters which make these optimisation problems admit fixed-parameter algorithms.

    In the second part of the thesis, we explore the approximability properties of the (weighted) Max CSP problem for graphs. This is a problem which is known to be approximable within some constant ratio, but not believed to be approximable within an arbitrarily small constant ratio. Thus it is of interest to determine the best ratio within which the problem can be approximated, or at least give some bound on this constant. We introduce a novel method for studying approximation ratios which, in the context of Max CSP for graphs, takes the form of a new binary parameter on the space of all graphs. This parameter may, informally, be thought of as a sort of distance between two graphs; knowing the distance between two graphs, we can bound the approximation ratio of one of them, given a bound for the other.

  • 6.
    Färnqvist, Tommy
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Heintz, Fredrik
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.
    Lambrix, Patrick
    Linköping University, Department of Computer and Information Science, Database and information techniques. Linköping University, The Institute of Technology.
    Mannila, Linda
    Åbo Academy, Finland.
    Wang, Chunyan
    Linköping University, Department of Computer and Information Science.
    Supporting Active Learning by Introducing an Interactive Teaching Tool in a Data Structures and Algorithms Course2016In: Proceedings of the 47th ACM Technical Symposium on Computer Science Education (SIGCSE 2016), ACM Publications, 2016, p. 663-668Conference paper (Refereed)
    Abstract [en]

    Traditionally, theoretical foundations in data structures and algorithms (DSA) courses have been covered through lectures followed by tutorials, where students practise their understanding on pen-and-paper tasks. In this paper, we present findings from a pilot study on using the interactive e-book OpenDSA as the main material in a DSA course. The goal was to redesign an already existing course by building on active learning and continuous examination through the use of OpenDSA. In addition to presenting the study setting, we describe findings from four data sources: final exam, OpenDSA log data, pre and post questionnaires as well as an observation study. The results indicate that students performed better on the exam than during previous years. Students preferred OpenDSA over traditional textbooks and worked actively with the material, although a large proportion of them put off the work until the due date approaches.

  • 7.
    Färnqvist, Tommy
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Heintz, Fredrik
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.
    Lambrix, Patrick
    Linköping University, Department of Computer and Information Science, Database and information techniques. Linköping University, The Institute of Technology.
    Mannila, Linda
    Åbo Academy, Finland.
    Wang, Chunyan
    Linköping University, Department of Computer and Information Science.
    Supporting Active Learning Using an Interactive Teaching Tool in a Data Structures and Algorithms Course2015In: Proceedings of 5:e Utvecklingskonferensen för Sveriges ingenjörsutbildningar (UtvSvIng), 2015, p. 76-79Conference paper (Other academic)
    Abstract [en]

    Traditionally, theoretical foundations in data structuresand algorithms (DSA) courses have been covered throughlectures followed by tutorials, where students practise theirunderstanding on pen-and-paper tasks. In this paper, we presentfindings from a pilot study on using the interactive e-bookOpenDSA as the main material in a DSA course. The goal was toredesign an already existing course by building on active learningand continuous examination through the use of OpenDSA. Inaddition to presenting the study setting, we describe findings fromfour data sources: final exam, OpenDSA log data, pre- and postcourse questionnaires as well as an observation study. The resultsindicate that students performed better on the exam than duringprevious years. Students preferred OpenDSA over traditionaltextbooks and worked actively with the material, although alarge proportion of them put off the work until the due dateapproaches.

  • 8.
    Färnqvist, Tommy
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Bounded Tree-Width and CSP-Related Problems2007In: Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007. Proceedings / [ed] Takeshi Tokuyama, Springer Berlin/Heidelberg, 2007, p. 632-643Chapter in book (Refereed)
    Abstract [en]

    We study the complexity of structurally restricted homomorphism and constraint satisfaction problems. For every class of relational structures C , let LHom be the problem of deciding whether a structure A Î CA has a homomorphism to a given arbitrary structure B, when each element in A is only allowed a certain subset of elements of B as its image. We prove, under a certain complexity-theoretic assumption, that this list homomorphism problem is solvable in polynomial time if and only if all structures in C have bounded tree-width. The result is extended to the connected list homomorphism, edge list homomorphism, minimum cost homomorphism and maximum solution problems. We also show an inapproximability result for the minimum cost homomorphism problem.

  • 9.
    Färnqvist, Tommy
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Thapper, Johan
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Approximability Distance in the Space of H-Colourability Problems2009In: COMPUTER SCIENCE - THEORY AND APPLICATIONS, ISSN 0302-9743, Vol. 5675, p. 92-104Article in journal (Refereed)
    Abstract [en]

    A graph homomorphism is a vertex map which carries edges from a source graph to edges in a target graph. We Study the approximability properties of the Weigh feel Maximum H-Colourable Subgraph problem (MAX H-COL). The instances of this problem are edge-weighted graphs G and the objective is to find a subgraph of G that has maximal total edge weight, under the condition that the subgraph has a homomorphism to H note that for H = K-k this problem is equivalent to MAX k-CUT. To this end, we introduce a metric structure on the space of graphs which allows us to extend previously known approximability results to larger classes of graphs. Specifically, the approximation algorithms for MAX CUT by Goemans and Williamson and MAX k-CUT by Frieze and Jerrum can he used to yield non-trivial approximation results for MAX H-COL For a variety of graphs, we show near-optimality results under the Unique Games Conjecture. We also use our method for comparing the performance of Frieze andamp; Jerrums algorithm with Hastads approximation algorithm for general MAX 2-CSP. This comparison is, in most cases, favourable to Frieze andamp; Jerrum.

  • 10.
    Heintz, Fredrik
    et al.
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
    Färnqvist, Tommy
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Pedagogical Experiences of Competitive Elements in an Algorithms Course2012In: Proceedings of LTHs 7:e Pedagogiska Inspirationskonferens (PIK), 2012Conference paper (Refereed)
    Abstract [en]

    We claim that competitive elements can improve thequality of programming and algorithms courses. To test this, weused our experience from organising national and internationalprogramming competitions to design and evaluate two differentcontests in an introductory algorithms course. The first contestturned lab assignments into a competition, where two groups rancompetitions and two were control groups and did not compete.The second, voluntary, contest, consisting of 15 internationalprogramming competition style problems, was designed tosupport student skill acquisition by providing them withopportunities for deliberate practise. We found that competitiveelements do influence student behaviour and our mainconclusions from the experiment are that students really likecompetitions, that the competition design is very important forthe resulting behaviour of the students, and that active studentsperform better on exams.

    We also report on an extra-curricular activity in the form of asemester long programming competition as a way of supportingstudent's deliberate practise in computer programming.

  • 11.
    Heintz, Fredrik
    et al.
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Intergrated Computer systems. Linköping University, The Institute of Technology.
    Färnqvist, Tommy
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Återkoppling genom automaträttning2013In: Proceedings of 4:de Utvecklingskonferensen för Sveriges ingenjörsutbildningar (UtvSvIng), 2013Conference paper (Refereed)
    Abstract [sv]

    Vi har undersökt olika former av återkoppling genom automaträttning i en kurs i datastrukturer och algoritmer. 2011 undersökte vi effekterna av tävlingsliknande moment som också använder automaträttning. 2012 införde vi automaträttning av laborationerna. Vi undersökte då hur återkoppling genom automaträttning påverkar studenternasarbetssätt, prestationsgrad och relation till den examinerande personalen. Genom automaträttning får studenterna omedelbar återkoppling om deras program är tillräckligt snabbt och ger rätt svar på testdata. När programmet är korrekt och resurseffektivt kontrollerar kursassistenterna att programmet även uppfyller andra krav som att vara välskrivet och välstrukturerat. Efter kursen undersökte vi studenternas inställning till och upplevelse av automaträttning genom en enkät. Resultaten är att studenterna är positiva till automaträttning (80% av alla som svarade) och att den påverkade studenternas sätt att arbeta huvudsakligen positivt. Till exempel svarade 50% att de ansträngde sig hårdare tack vare automaträttningen. Dessutom blir rättningen mer objektiv då den görs på exakt samma sätt för alla. Vår slutsats är att återkoppling genom automaträttning ger positiva effekter och upplevs som positiv av studenterna.

  • 12.
    Heintz, Fredrik
    et al.
    Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.
    Färnqvist, Tommy
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Thorén, Jesper
    Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
    Programutvecklingsstrategier för att öka kopplingen mellan programmering och matematik2015In: Proceedings of 5:e Utvecklingskonferensen för Sveriges ingenjörsutbildningar (UtvSvIng), 2015Conference paper (Refereed)
    Abstract [sv]

    Matematik och programmering är två viktiga inslag i civilingenjörsprogram inom data- och mjukvaruteknik. De studenter som klarar dessa kurser klarar sannolikt resten av utbildningen. Idag har fler studenter programmering än matematik som huvudsakligt intresse. Därför har Linköpings universitet aktivt jobbat med olika strategier för att öka kopplingen mellan programmering och matematik, främst i de inledande kurserna. För att undersöka studenternas attityder till matematik och programmering har vi genomfört flera enkätstudier som bl.a. visar att intresset för matematik är stort men intresset för programmering ännu större och att studenterna tror de kommer ha betydligt mer nytta av programmering än matematik under sin karriär. Texten är tänkt som grund för en diskussion kring hur kopplingarna mellan matematik och programmering kan göras tydligare och starkare.

1 - 12 of 12
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf