Publications of Pinar Heggernes

Algorithms and combinatorial results for graph classes
These results mainly concern solving graph problems that are NP-hard in general, on graphs with certain structure. Tractability is obtaied via polynomial-time or fixed parameter tractable algorithms. In this category are also algorithms for recognizing graphs with certain structure, and combinatorial results like characterizations of graph classes or other structural properties.

Graph modification problems
These problems concern modifying a given arbitrary graph by adding, removing, or contracting edges, or removing vertices, to obtain certain properties, typically membership in a desired graph class.

Miscellaneous
These results concern polynomial-time, exact exponential time or fixed parameter tractable algorithms for general input. The studied problems are decompositions, partitioning, and ordering. Some of my old results on sparse matrices are also here.

Teaching related
Some lecture notes and handouts for algorithms classes.

Theses
My PhD and Master theses.

Algorithms and combinatorial results for graph classes

Generation of random chordal graphs using subtrees of a tree
Oylum Seker, Pinar Heggernes, Tinaz Ekim, and Caner Taskin
Full version to appear in RAIRO - Operations Research.
(Preliminary version appeared as CIAC 2017, LNCS 10236: 442-453, Springer.)

On the maximum number of edges in chordal graphs of bounded degree and matching number
Jean R. S. Blair, Pinar Heggernes, Daniel Lokshtanov, Paloma T. Lima
Full version to appear in Algorithmica.
(Preliminary version (open access) appeared as LATIN 2020, LNCS 12118: 600-612, Springer.)

Enumeration of minimal connected dominating sets for chordal graphs
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Reza Saei
Discrete Applied Mathematics 278: 3-11 (2020)

Partitioning a graph into degenerate subgraphs (open access)
Faisal Abu-Khzam, Carl Feghali, and Pinar Heggernes
European Journal of Combinatorics 83 (2020)

Parameterized Aspects of Strong Subgraph Closure
Petr A. Golovach, Pinar Heggernes, Athanasios L. Konstantinidis, Paloma T. Lima, Charis Papadopoulos
Algorithmica 82: 2006-2038 (2020)
(Preliminary version appeared as SWAT 2018, LIPIcs 101: 23:1-23:13.)

Finding connected secluded subgraphs (pdf)
Petr A. Golovach, Pinar Heggernes, Paloma T. Lima, and Pedro Montealegre
Journal of Computer and System Sciences 113: 101-124 (2020)
(Preliminary version appeared as IPEC 2017, LIPIcs 89: 18:1-18:13.)

Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2 (pdf)
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Paloma T. Lima, and Daniel Paulusma
Algorithmica 81: 2795-2828 (2019)
(Preliminary version appeared as WG 2017, LNCS 10520: 275-288, Springer.)

Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs (pdf)
Pinar Heggernes, Davis Issac, Juho Lauri, Paloma T. Lima, Erik Jan van Leeuwen
MFCS 2018, LIPIcs 117: 83:1-83:13

Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs (pdf)
Petr A. Golovach, Pinar Heggernes, and Dieter Kratsch
European Journal of Combinatorics 68: 132-147 (2018)
(Preliminary version appeared as IWOCA 2015, LNCS 9538: 235-247, Springer.)

Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-width (pdf)
Petr A. Golovach, Pinar Heggernes, Mamadou Kante, Dieter Kratsch, Sigve Sæther, and Yngve Villanger
Algorithmica 68: 132-147 (2018)
(Preliminary version appeared as ISAAC 2015, LNCS 9472: 248-258, Springer.)

Definability Equals Recognizability for k-Outerplanar Graphs and l-Chordal Partial k-Trees (pdf)
Hans L. Bodlaender, Pinar Heggernes, Lars Jaffke, and Jan Arne Telle
European Journal of Combinatorics 66: 191-234 (2017)
(Preliminary version appeared as EUROCOMB 2015, Electronic Notes in Discrete Mathematics 49: 559-568.)

Maximum number of edges in claw-free graphs whose maximum degree and matching number are bounded (pdf)
Cemil Dibek, Tinaz Ekim, and Pinar Heggernes
Discrete Mathematics 340: 927-934 (2017)

Minimal dominating sets in interval graphs and trees (pdf)
Petr A. Golovach, Pinar Heggernes, Mamadou Kante, Dieter Kratsch, and Yngve Villanger
Discrete Applied Mathematics 216: 162-170 (2017).

On Recognition of Threshold Tolerance Graphs and their Complements (pdf)
Petr A. Golovach, Pinar Heggernes, Nathan Lindzey, Ross McConnell, Vincius dos Santos, Jeremy Spinrad, and Jayme Szwarcfiter
Dicrete Applied Mathematics 216: 171-180 (2017).
(Preliminary version appeared as WG 2014, LNCS 8747: 214-224, Springer.)

Enumerating minimal dominating sets in chordal graphs (pdf)
Faisal Abu-Khzam and Pinar Heggernes
Information Processing Letters 116: 739-743 (2016).

Maximal induced matchings in triangle-free graphs (pdf)
Manu Basavaraju, Pinar Heggernes, Pim van 't Hof, Reza Saei, and Yngve Villanger
Journal of Graph Theory 83: 231-215 (2016)
(Preliminary version appeared as WG 2014, LNCS 8747: 93-104, Springer.)

Clique-width of path powers (pdf)
Pinar Heggernes, Daniel Meister, Charis Papadopoulos, and Udi Rotics
Discrete Applied Mathematics 205: 62-72 (2016).
(Preliminary versions of different parts appeared as TAMC 2009, LNCS 5532: 241-250; and CSR 2011, LNCS 6651: 233-246, Springer.)

Enumerating minimal connected dominating sets in graphs of bounded chordality (pdf)
Petr Golovach, Pinar Heggernes, and Dieter Kratsch
Theoretical Computer Science 630: 63-75 (2016).
(Preliminary version appeared as IPEC 2015, LIPIcs 43: 307-318, Leibniz-Zentrum fur Informatik.)

The Firefighter Problem on Graph Classes (pdf)
Fedor Fomin, Pinar Heggernes, and Erik Jan van Leeuwen
Theoretical Computer Science 613: 38-50 (2016).
(Preliminary version appeared as FUN 2012, LNCS 7288: 177-188, Springer.)

Enumerating minimal dominating sets in chordal bipartite graphs (pdf)
Petr Golovach, Pinar Heggernes, Mamadou Kante, Dieter Kratsch, and Yngve Villanger
Discrete Applied Mathematics 199: 30-36 (2016).

Foreword: Sixth Workshop on Graph Classes, Optimization, and Width Parameters, Santorini, Greece, October 2013 (pdf)
Pinar Heggernes, Andrzej Proskurowski, and Dimitrios Thilikos
Discrete Applied Mathematics 199: 1-2 (2016).

Hadwiger Number of Graphs with Small Chordality (pdf)
Petr Golovach, Pinar Heggernes, Pim van 't Hof, and Christophe Paul
SIAM Journal on Discrete Mathematics 29: 1427-1451 (2015).
(Preliminary version appeared as WG 2014, LNCS 8747: 201-213, Springer.)

Computing the metric dimension for chain graphs
Henning Fernau, Pinar Heggernes, Pim van 't Hof, Daniel Meister, and Reza Saei
Information Processing Letters 115: 671-676 (2015).

Finding Disjoint Paths in Split Graphs (pdf)
Pinar Heggernes, Pim van 't Hof, Erik Jan van Leeuwen and Reza Saei
Theory of Computing Systems 57: 140-159 (2015).
(Preliminary version appeared as SOFSEM 2014, LNCS 8327: 315-326, Springer.)

An incremental polynomial time algorithm to enumerate all minimal edge dominating sets (pdf)
Petr Golovach, Pinar Heggernes, Dieter Kratsch, and Yngve Villanger
Algorithmica 72: 836-859 (2015).
(Prelimiary version appeared as ICALP 2013, Part I, LNCS 7965: 485-496, Springer.)

Induced Subgraph Isomorphism on proper interval and bipartite permutation graphs (pdf)
Pinar Heggernes, Pim van 't Hof, Daniel Meister, and Yngve Villanger
Theoretical Computer Science 562: 252-269 (2015).
(Preliminary version appeared as ISAAC 2010, LNCS 6507: 399-409, Springer. However, we discovered flaws in the proofs of Theorems 1 and 2 in the ISAAC version. Please consider these two results as so far unverified.)

Scheduling unit-length jobs with precedence constraints of small height (pdf)
Andre Berger, Alexander Grigoriev, Pinar Heggernes, and Ruben van der Zwaan
Operations Research Letters 42: 166-172 (2014).

Vector Connectivity in Graphs (pdf)
Endre Boros, Pinar Heggernes, Pim van 't Hof, and Martin Milanic
Networks 63: 277-285 (2014).
(Preliminary version appeared as TAMC 2013, LNCS 7876: 331-342, Springer.)

Finding clubs in graph classes (pdf)
Petr Golovach, Pinar Heggernes, Dieter Kratsch, and Arash Rafiey
Discrete Applied Mathematics 174: 57-65 (2014).
(Preliminary version appeared as CIAC 2013, LNCS 7878: 276-287, Springer.)

Graph classes and Ramsey numbers (pdf)
Remy Belmonte, Pinar Heggernes, Pim van 't Hof, Arash Rafiey, and Reza Saei
Discrete Applied Mathematics 173: 16-27 (2014).
(Preliminary version appeared as COCOON 2012 (best paper award), LNCS 7434: 204-215, Springer.)

An exact algorithm for Subset Feedback Vertex Set on chordal graphs (pdf)
Petr Golovach, Pinar Heggernes, Dieter Kratsch, and Reza Saei
Journal of Discrete Algorithms 26: 7-15 (2014).
(Preliminary version appeared as IPEC 2012, LNCS 7537: 85-96, Springer.)

Detecting fixed patterns in chordal graphs in polynomial time (pdf)
Remy Belmonte, Petr Golovach, Pinar Heggernes, Pim van 't Hof, Marcin Kaminski, and Daniel Paulusma
Algorithmica 69: 501-521 (2014).
(Preliminary version appeared as ISAAC 2011, LNCS 7074: 110-119, Springer.)

Contracting chordal graphs and bipartite graphs to paths and trees (pdf)
Pinar Heggernes, Pim van 't Hof, Benjamin Leveque, and Christophe Paul
Discrete Applied Mathematics 164: 444-449 (2014).
(Preliminary version appeared as LAGOS 2011, Electronic Notes in Discrete Mathematics 37: 87-92.)

Fifth Workshop on Graph Classes, Optimization, and Width Parameters - Daejeon, South Korea - October 2011 (pdf)
Pinar Heggernes, Jan Kratochvil, Sang-il Oum (guest editors)
Discrete Applied Mathematics 168 (2014).

Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing via iterative localization (pdf)
Pinar Heggernes, Dieter Kratsch, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh
Information and Computation 231 (2013): 109-116.
(Preliminary version appeared as SWAT 2010, LNCS 6139: 334-345, Springer.)

Minimal dominating sets in graph classes: combinatorial bounds and enumeration (pdf)
Jean-François Couturier, Pinar Heggernes, Pim van 't Hof, and Dieter Kratsch
Theoretical Computer Science 487 (2013): 82-94.
(Preliminary version appeared as SOFSEM 2012, LNCS 7147: 202-213, Springer.)

Choosability on H-free graphs (pdf)
Petr Golovach, Pinar Heggernes, Pim van 't Hof, and Daniel Paulusma
Information Processing Letters 113 (2013): 107-110.

Polar permutation graphs are polynomial-time recognisable (pdf)
Tınaz Ekim, Pinar Heggernes, and Daniel Meister
European Journal of Combinatorics 34 (2013) 576-592.
(Preliminary version appeared as IWOCA 2009, LNCS 5874: 218-229, Springer.)

Induced subtrees in interval graphs (pdf)
Pinar Heggernes, Pim van 't Hof, and Martin Milanic
IWOCA 2013, LNCS 8288: 230-241, Springer.

Maximum number of minimal feedback vertex sets in chordal graphs and cographs (pdf)
Jean-François Couturier, Pinar Heggernes, Pim van 't Hof, and Yngve Villanger
COCOON 2012, LNCS 7434: 133-144, Springer.

Broadcast Domination on block graphs in linear time (pdf)
Pinar Heggernes and Sigve H. Sæther
CSR 2012, LNCS 7353: 177-188, Springer.

Computing minimum geodetic sets in proper interval graphs (pdf)
Tinaz Ekim, Aysel Erey, Pinar Heggernes, Pim van 't Hof, and Daniel Meister
LATIN 2012, LNCS 7256: 279-290, Springer.

Computing the cutwidth of bipartite permutation graphs in linear time (pdf)
Pinar Heggernes, Pim van 't Hof, Daniel Lokshtanov, and Jesper Nederlof
SIAM Journal of Discrete Mathematics 26 (2012): 1008-1021.
(Preliminary version appeared as WG 2010, LNCS 6410: 75-87, Springer.)

Edge contractions in subclasses of chordal graphs (pdf)
Remy Belmonte, Pinar Heggernes, and Pim van 't Hof
Discrete Applied Mathematics 160 (2012): 999-1010.
(Preliminary version appeared as TAMC 2011, LNCS 6648: 528-539, Springer.)

Computing role assignments of proper interval graphs in polynomial time (pdf)
Pinar Heggernes, Pim van 't Hof, and Daniel Paulusma
Journal of Discrete Algorithms 14 (2012): 173-188.
(Preliminary version appeared as IWOCA 2010, LNCS 6460: 167-180, Springer.)

Fourth Workshop on Graph Classes, Optimization, and Width Parameters - Bergen, Norway - October 2009 (pdf)
Pinar Heggernes, Jan Kratochvil, and Andrzej Proskurowski (guest editors)
Discrete Applied Mathematics 160-6 (2012): 683-921.

Edge search number of cographs (pdf)
Petr Golovach, Pinar Heggernes, and Rodica Mihai
Discrete Applied Mathematics 160 (2012): 734-743.
(Preliminary version of some part appeared as FAW 2009, LNCS 5598: 16-26, Springer.)

Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs (pdf)
Pinar Heggernes, Daniel Meister, and Charis Papadopoulos
Discrete Applied Mathematics 160 (2012): 888-901.

Cutwidth of split graphs and threshold graphs (pdf)
Pinar Heggernes, Daniel Lokshtanov, Rodica Mihai, and Charis Papadopoulos
SIAM Journal on Discrete Mathematics 25 (2011): 1418-1437.
(Preliminary version appeared as WG 2008, LNCS 5344: 218-229, Springer.)

Bandwidth on AT-free graphs (pdf)
Petr Golovach, Pinar Heggernes, Dieter Kratsch, Daniel Lokshtanov, Daniel Meister, and Saket Saurabh
Theoretical Computer Science, 412 (2011) : 7001-7008.
(Preliminary version appeared as ISAAC 2009, LNCS 5878: 573-582, Springer.)

Strongly chordal and chordal bipartite graphs are sandwich monotone (pdf)
Pinar Heggernes, Federico Mancini, Charis Papadopoulos, and R. Sritharan
Journal of Combinatorial Optimization 22 (2011) : 438-456.
(Preliminary version appeared as COCOON 2009, LNCS 5609: 398-407, Springer.)

Graphs of linear clique-width at most 3 (pdf)
Pinar Heggernes, Daniel Meister, and Charis Papadopoulos
Theoretical Computer Science 412 (2011): 5466-5486.
(Preliminary version appeared as TAMC 2008, LNCS 4978: 330-341, Springer.)

Computing minimum distortion embeddings into a path of bipartite permutation graphs and threshold graphs (pdf)
Pinar Heggernes, Daniel Meister, and Andrzej Proskurowski
Theoretical Computer Science 412 (2011): 1275-1297.
(Preliminary version appeared as SWAT 2008, LNCS 5124: 331-342, Springer.)

Third Workshop on Graph Classes, Optimization, and Width Parameters - Eugene, Oregon, USA - October 2007 (pdf)
Pinar Heggernes, Jan Kratochvil, and Andrzej Proskurowski (guest editors)
Discrete Applied Mathematics 158-7 (2010): 729-868.

Mixed search number and linear-width of interval and split graphs (pdf)
Fedor Fomin, Pinar Heggernes, and Rodica Mihai
Networks 56 (2010): 207-214.
(Preliminary version appeared as WG 2007, LNCS 4769: 304-315, Springer.)

Hardness and approximation of minimum distortion embeddings (pdf)
Pinar Heggernes and Daniel Meister
Information Processing Letters 110 (2010): 312-316.

Exploiting restricted linear structure to cope with the hardness of clique-width (pdf)
Pinar Heggernes, Daniel Meister, and Udi Rotics
TAMC 2010, LNCS 6108: 284-295, Springer.

Bandwidth of bipartite permutation graphs in polynomial time (pdf)
Pinar Heggernes, Dieter Kratsch, and Daniel Meister
Journal of Discrete Algorithms 7 (2009): 533-544.
(Preliminary version appeared as LATIN 2008, LNCS 4957: 216-227, Springer.)

Choosability of P₅-free graphs (pdf)
Petr Golovach and Pinar Heggernes
MFCS 2009, LNCS 5734: 382-391, Springer.

A new representation of proper interval graphs with an application to clique-width (pdf)
Pinar Heggernes, Daniel Meister, and Charis Papadopoulos
DIMAP Workshop on Algorithmic Graph Theory 2009, Electronic Notes in Discrete Mathematics 32 (2009): 27-34.

Mixed search number of permutation graphs (pdf)
Pinar Heggernes and Rodica Mihai
FAW 2008, LNCS 5059: 196-207, Springer.

Linear-time certifying recognition algorithms and forbidden induced subgraphs (pdf)
Pinar Heggernes and Dieter Kratsch
Nordic Journal of Computing 14 (2007): 87-108. (Printed in 2008)

Optimal linear arrangement of interval graphs (pdf)
Johanne Cohen, Fedor Fomin, Pinar Heggernes, Dieter Kratsch, and Gregory Kucherov
MFCS 2006, LNCS 4162: 267 - 279, Springer.

Broadcast Domination Algorithms for Interval Graphs, Series-Parallel Graphs, and Trees (ps) (pdf)
Jean Blair, Pinar Heggernes, Steve Horton, and Fredrik Manne
CGTC 2004, Congressus Numerantium 169: 55 - 77.

Generalized H-coloring and H-covering of Trees (ps, pdf)
Jiri Fiala, Pinar Heggernes, Petter Kristiansen, and Jan Arne Telle
Nordic Journal of Computing 10-3 (2003): 206-224.
(Preliminary version appeared as WG 2002, LNCS 2573: 198-210, Springer.)

Recognizing Weakly Triangulated Graphs by Edge Separability (ps, pdf)
Anne Berry, Jean-Paul Bordat, and Pinar Heggernes
Nordic Journal of Computing 7-3 (2000): 164-177.
(Preliminary version appeared as SWAT 2000, LNCS 1851: 139-149, Springer.)

Finding Minimum Height Elimination Trees for Interval Graphs in Polynomial Time (ps, pdf)
Bengt Aspvall and Pinar Heggernes
BIT 34-4 (1994): 484 -509.
(Preliminary version appeared at NIK 1993, Tapir Forlag.)

Graph modification problems

Modifying a Graph Using Vertex Elimination (pdf)
Petr Golovach, Pinar Heggernes, Pim van 't Hof, Fredrik Manne, Daniel Paulusma, and Michal Pilipzcuk
Algorithmica 72: 99-125 (2015).
(Preliminary version appeared as WG 2012, LNCS 7551: 320-331, Springer.)

Contracting Graphs to Paths and Trees (pdf)
Pinar Heggernes, Pim van 't Hof, Benjamin Leveque, Daniel Lokshtanov, and Christophe Paul
Algorithmica 68 (2014): 109-132.
(Prelimiary version appeared as IPEC 2011, LNCS 7112, Springer.)

Obtaining a Bipartite Graph by Contracting Few Edges (pdf)
Pinar Heggernes, Pim van 't Hof, Daniel Lokshtanov, and Christophe Paul
SIAM Journal on Discrete Mathematics 27 (2013): 2143-2156.
(Preliminary version appeared as FSTTCS 2011, LIPIcs 13: 217-228, Leibniz-Zentrum fur Informatik.)

Parameterized Complexity of Vertex Deletion into Perfect Graph Classes (pdf)
Pinar Heggernes, Pim van 't Hof, Bart Jansen, Stefan Kratsch, and Yngve Villanger
Theoretical Computer Science 511 (2013): 172-180.
(Preliminary version appeared as FCT 2011, LNCS 6914: 240-251, Springer.)

Faster parameterized algorithms for Minimum Fill-In (pdf)
Hans Bodlaender, Pinar Heggernes, and Yngve Villanger
Algorithmica 61 (2011): 817-83.
(Preliminary version appeared as ISAAC 2008, LNCS 5369: 282-293, Springer.)

Clustering with partial information (pdf)
Hans Bodlaender, Mike Fellows, Pinar Heggernes, Federico Mancini, Charis Papadopoulos, and Frances Rosamond
Theoretical Computer Science 411 (2010): 1202-1211.
(Preliminary version appeared as MFCS 2008, LNCS 5162: 144-155, Springer.)

Generalized graph clustering: recognizing (p,q)-cluster graphs (pdf)
Pinar Heggernes, Daniel Lokshtanov, Jesper Nederlof, Christophe Paul, and Jan Arne Telle
WG 2010, LNCS 6410: 171-183, Springer.

A parameterized algorithm for Chordal Sandwich (pdf)
Pinar Heggernes, Federico Mancini, Jesper Nederlof, and Yngve Villanger
CIAC 2010, LNCS 6078: 120-130, Springer.

Interval Completion is Fixed Parameter Tractable (pdf)
Yngve Villanger, Pinar Heggernes, Christophe Paul, and Jan Arne Telle
SIAM Journal on Computing 38-5 (2009): 2007-2020.
(Preliminary version appeared as STOC 2007: 374-381, ACM.)

Minimal split completions (pdf)
Pinar Heggernes and Federico Mancini
Discrete Applied Mathematics 157 (2009): 2659-2669.
(Preliminary version appeared as LATIN 2006, LNCS 3887: 592 - 604, Springer.)

Dynamically maintaining split graphs (pdf)
Pinar Heggernes and Federico Mancini
Discrete Applied Mathematics 157 (2009): 2057-2069.
(Preliminary version appeared as ODSA 2006, Electronic Notes in Discrete Mathematics 27 (2006): 27-34.)

Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions (pdf)
Pinar Heggernes and Charis Papadopoulos
Theoretical Computer Science 410-1 (2009): 1-15.
(Preliminary version appeared as COCOON 2007, LNCS 4598: 406-416, Springer.)

Sequential and parallel triangulating algorithms for Elimination Game and new insights on Minimum Degree (pdf)
Anne Berry, Elias Dahlhaus, Pinar Heggernes, and Genevieve Simonet
Theoretical Computer Science 409-3 (2008): 601-616.
(Preliminary version appeared as WG 2003, LNCS 2880: 58 - 70, Springer.)

Fast computation of minimal fill inside a given elimination ordering (pdf)
Pinar Heggernes and Barry Peyton
SIAM Journal on Matrix Analysis and Applications 30-4 (2008): 1424-1444.

Minimal comparability completions of arbitrary graphs (pdf)
Pinar Heggernes, Federico Mancini, and Charis Papadopoulos
Discrete Applied Mathematics 156 (2008): 705-718.
(Preliminary version appeared as ISAAC 2006, LNCS 4288: 419 - 428, Springer.)

Characterizing minimal interval completions: Towards better understanding of profile and pathwidth (ps)
Pinar Heggernes, Karol Suchan, Ioan Todinca, and Yngve Villanger
STACS 2007, LNCS 4393: 236 - 247, Springer.

Minimal triangulations of graphs: A survey (ps, pdf)
Pinar Heggernes
Discrete Mathematics 306-3 (2006): 297-317.

A vertex incremental approach for maintaining chordality (ps, pdf)
Anne Berry, Pinar Heggernes, and Yngve Villanger
Discrete Mathematics 306-3 (2006): 318-336.
(Preliminary version appeared as ISAAC 2003, LNCS 2906: 47 - 57, Springer.)

A wide-range algorithm for minimal triangulation from an arbitrary ordering (ps, pdf)
Anne Berry, Jean-Paul Bordat, Pinar Heggernes, Genevieve Simonet, and Yngve Villanger
Journal of Algorithms 58-1 (2006): 33 - 66.

Computing Minimal Triangulations in Time O(n^α log n) = o(n^2.376) (ps, pdf)
Pinar Heggernes, Jan Arne Telle, and Yngve Villanger
SIAM Journal on Discrete Mathematics 19-4 (2005): 900 - 913.
(Preliminary version appeared as SODA 2005: 907 - 916, ACM-SIAM.)

Minimal interval completions (ps) (pdf)
Pinar Heggernes, Karol Suchan, Ioan Todinca, and Yngve Villanger
ESA 2005, LNCS 3669: 403 - 414, Springer.

Maximum Cardinality Search for Computing Minimal Triangulations of Graphs (ps, pdf)
Anne Berry, Jean Blair, Pinar Heggernes, and Barry Peyton
Algorithmica 39-4 (2004): 287 - 298.
(Preliminary version appeared as WG 2002, LNCS 2573: 1-12, Springer.)

A Practical Algorithm for Making Filled Graphs Minimal (ps, pdf)
Jean Blair, Pinar Heggernes, and Jan Arne Telle
Theoretical Computer Science 250-1/2 (2001): 125-141.
(Preliminary version appeared as SWAT 1996, LNCS 1097: 173-184, Springer.)

Simple and Efficient Modifications of Elimination Orderings (pdf)
Pinar Heggernes and Yngve Villanger
PARA 2004, LNCS 3732: 788 - 797, Springer.

Efficient Implementation of a Minimal Triangulation Algorithm (ps) (pdf)
Pinar Heggernes and Yngve Villanger
ESA 2002, LNCS 2461: 550-561, Springer.

The Computational Complexity of the Minimum Degree Algorithm (ps) (pdf)
Pinar Heggernes, Stanley Eisenstat, Gary Kumfert, and Alex Pothen
NIK 2001: 98 - 109.
(Also available as ICASE Report 2001-42, NASA/CR-2001-211421, NASA Langley Research Center, USA.)

Reducing the fill-in size for an elimination tree (ps) (pdf)
Pinar Heggernes
IMA Workshop on Sparse Matrix Computations: Graph Theory Issues and Algorithms, Minneapolis, USA, 1991.

Miscellaneous

44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019
Peter Rossmanith, Pinar Heggernes, Joost-Pieter Katoen (editors)
LIPIcs 138, Leibniz-Zentrum fur Informatik (2019).

Algorithms and Complexity - 11th International Conference, CIAC 2019
Pinar Heggernes (editor)
LNCS 11485, Springer (2019).

Preface: Algorithmic Graph Theory on the Adriatic Coast (pdf)
Bostjan Bresar, Pinar Heggernes, Marcin Kaminski, Martin Milanic, Daniel Paulusma, Primoz Potocnik, Nicolas Trotignon
Discrete Applied Mathematics 231: 1-3 (2017).

Graph-Theoretic Concepts in Computer Science - 42nd International Workshop, WG 2016
Pinar Heggernes (editor)
LNCS 9941, Springer (2016).

Foreword: Special Issue on IPEC 2014 (pdf)
Mareky Cygan and Pinar Heggernes
Algorithmica 75: 255-256 (2016).

A characterisation of clique-width through nested partitions (pdf)
Bruno Courcelle, Pinar Heggernes, Daniel Meister, Charis Papadopoulos, and Udi Rotics
Discrete Applied Mathematics 187: 70-81 (2015)

A Multi-Parameter Analysis of Hard Problems on Deterministic Finite Automata (pdf)
Henning Fernau, Pinar Heggernes, and Yngve Villanger
Journal of Computer and System Sciences 81: 747-765 (2015).
(Preliminary version appeared as LATA 2013, LNCS 7810: 275 - 286, Springer.)

On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties (pdf)
Pinar Heggernes, Pim van 't Hof, Daniel Marx, Neeldhara Misra, and Yngve Villanger
Algorithmica 72: 687-713 (2015).
(Preliminary version appeared as WG 2012, LNCS 7551: 332-343, Springer.)

Parameterized and Exact Computation - 9th International Symposium, IPEC 2014
Marek Cygan and Pinar Heggernes (editors)
LNCS 8894, Springer (2014).

Enumerating minimal subset feedback vertex sets (pdf)
Fedor Fomin, Pinar Heggernes, Dieter Kratsch, Charis Papadopoulos, and Yngve Villanger
Algorithmica 69-1: 216-231 (2014).
(Preliminary version appeared as WADS 2011, LNCS 6844: 399 - 410, Springer.)

A generic approach to decomposition algorithms, with an application to digraph decomposition (pdf)
Binh-Minh Bui-Xuan, Pinar Heggernes, Daniel Meister, and Andrzej Proskurowski
COCOON 2011, LNCS 6842: 331 - 342, Springer.

Exact Algorithms for Graph Homomorphisms (ps, pdf)
Fedor Fomin, Pinar Heggernes, and Dieter Kratsch
Theory of Computing Systems 41-2 (2007): 381-393.
(Preliminary version appeared as FCT 2005, LNCS 3623: 161 - 171, Springer.)

Optimal broadcast domination in polynomial time (ps, pdf)
Pinar Heggernes and Daniel Lokshtanov
Discrete Mathematics 306-24 (2006): 3267-3280.
(Preliminary version appeared as WG 2005, LNCS 3787: 187 - 198, Springer.)

Graph searching, elimination trees, and a generalization of bandwidth (ps, pdf)
Fedor Fomin, Pinar Heggernes, and Jan Arne Telle
Algorithmica 41-2 (2004): 73 - 87.
(Preliminary version appeared as FCT 2003, LNCS 2751: 73 - 85, Springer.)

Finding k disjoint triangles in an arbitrary graph (pdf)
Mike Fellows, Pinar Heggernes, Frances Rosamond, Christian Sloper, and Jan Arne Telle
WG 2004, LNCS 3353: 235 - 244, Springer.

Methods for Large Scale Total Least Squares Problems (ps, pdf)
Ake Bjorck, Pinar Heggernes, and Pontus Matstoms
SIAM Journal on Matrix Analysis and Applications 22-2 (2000): 413-429.

Partitioning Graphs Into Generalized Dominating Sets (ps, pdf)
Pinar Heggernes and Jan Arne Telle
Nordic Journal of Computing 5-2 (1998): 128-142.
(Preliminary version appeared as SCCC 1995 - XV International Conference of the Chilean Computer Society: 241-252.)

Finding Good Column Orderings for Sparse QR Factorization (ps) (pdf)
Pinar Heggernes and Pontus Matstoms
Second SIAM Conference on Sparse Matrices, Idaho, USA, 1996.
(Also available as Reports in Informatics 120, University of Bergen, 1996, and Report LiTH-MAT-R-1996-20, Linkoping University, Sweden.)

Scalable parallel algorithms for matrix multiplication by Gramian of Toeplitz-block matrix
Gabriel Oksa, Martin Becka, Marian Vajtersic, Randi Moe, Fredrik Manne, and Pinar Heggernes
Technical Report NATO/977203/3, Slovak Academy of Sciences, Bratislava, Slovakia, 2002.

Partitioning a Set of Functions into Correlated Subsets
Pinar Heggernes and Pontus Matstoms
VTI report 416A, Swedish National Road and Transport Research Institute, Linkoping, Sweden, 1998.

A Simple Cubic Algorithm for Computing Minimum Height Elimination Trees for Interval Graphs (ps) (pdf)
Bengt Aspvall, Pinar Heggernes, and Jan Arne Telle
Reports in Informatics 103, University of Bergen, 1995.

Teaching Related Publications

Treewidth, partial k-trees, and chordal graphs (ps) (pdf)
Pinar Heggernes
Partial curriculum in INF334 - Advanced algorithmical techniques, Department of Informatics, University of Bergen, Norway, 2005.

Det profesjonsorienterte studiet i IKT - Forslag til undervisning og studentvurdering
Pinar Heggernes and Richard Moe
In Universitetspedagogisk utviklingsarbeid i Bergen (Editor: I. Nordmo), UPED-skrift no. 2/02 (2002), University of Bergen, Norway.

Advanced Graph Theoretical Topics (ps) (pdf)
Pinar Heggernes
Partial curriculum in I238 - Algorithms II, Department of Informatics, University of Bergen, Norway, 2001.

Theses

Partitioning and Ordering Graphs for Sparse Matrix Computations (ps) (pdf)
Pinar Heggernes
PhD Thesis (1996), Department of Informatics, University of Bergen, Norway.

Minimizing Fill-in Size and Elimination Tree Height in Parallel Cholesky Factorization (ps) (pdf)
Pinar Heggernes,
Master's Thesis (1992), Department of Informatics, University of Bergen, Norway.