Martin Milanic

Mary Servatius

Eur. J. Comb., 2025

2024

Introduction: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2022 Special Issue.

[BibT_eX]

[DOI]

Daniel Dadush

Tami Tamir

ACM Trans. Algorithms, July, 2024

Treewidth versus clique number. II. Tree-independence number.

[BibT_eX]

[DOI]

J. Comb. Theory B, January, 2024

Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2024

A tame vs. feral dichotomy for graph classes excluding an induced minor or induced topological minor.

[BibT_eX]

[DOI]

CoRR, 2024

On Minimal Transversals of Maximal Cliques in Graphs.

[BibT_eX]

[DOI]

CoRR, 2024

Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star.

[BibT_eX]

[DOI]

Sebastian Wiederrecht

CoRR, 2024

Detecting K2, 3 as an induced minor.

[BibT_eX]

[DOI]

CoRR, 2024

Allocation of Indivisible Items with a Common Preference Graph: Minimizing Total Dissatisfaction.

[BibT_eX]

[DOI]

CoRR, 2024

The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs.

[BibT_eX]

[DOI]

Proceedings of the 19th Scandinavian Symposium and Workshops on Algorithm Theory, 2024

Detecting K2,3 as an Induced Minor.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 35th International Workshop, 2024

Computing Tree Decompositions with Small Independence Number.

[BibT_eX]

[DOI]

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Tree Decompositions Meet Induced Matchings: Beyond Max Weight Independent Set.

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

2023

Computing well-covered vector spaces of graphs using modular decomposition.

[BibT_eX]

[DOI]

Comput. Appl. Math., December, 2023

Fair allocation algorithms for indivisible items under structured conflict constraints.

[BibT_eX]

[DOI]

Comput. Appl. Math., October, 2023

Allocation of indivisible items with individual preference graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., July, 2023

Fair Allocation of Indivisible Items with Conflict Graphs.

[BibT_eX]

[DOI]

Algorithmica, May, 2023

Bisimplicial separators.

[BibT_eX]

[DOI]

CoRR, 2023

Minimizing Maximum Dissatisfaction in the Allocation of Indivisible Items under a Common Preference Graph.

[BibT_eX]

[DOI]

CoRR, 2023

Dually conformal hypergraphs.

[BibT_eX]

[DOI]

CoRR, 2023

Treewidth is NP-Complete on Cubic Graphs (and related results).

[BibT_eX]

[DOI]

CoRR, 2023

Functionality of box intersection graphs.

[BibT_eX]

[DOI]

CoRR, 2023

Upper Clique Transversals in Graphs.

[BibT_eX]

[DOI]

Yushi Uno

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2023

Treewidth Is NP-Complete on Cubic Graphs.

[BibT_eX]

[DOI]

Proceedings of the 18th International Symposium on Parameterized and Exact Computation, 2023

2022

Computer-assisted verification of confining two-rooted graphs with certain cages.

[BibT_eX]

[DOI]

Dataset, August, 2022

Complexity and algorithms for constant diameter augmentation problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2022

Shifting paths to avoidable ones.

[BibT_eX]

[DOI]

J. Graph Theory, 2022

Avoidable vertices and edges in graphs: Existence, characterization, and applications.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2022

Conditions for minimally tough graphs.

[BibT_eX]

[DOI]

CoRR, 2022

Tree decompositions with bounded independence number: beyond independent sets.

[BibT_eX]

[DOI]

Pawel Rzazewski

CoRR, 2022

Avoidability beyond paths.

[BibT_eX]

[DOI]

CoRR, 2022

On Constrained Intersection Representations of Graphs and Digraphs.

[BibT_eX]

[DOI]

Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

2021

Strong cliques in diamond-free graphs.

[BibT_eX]

[DOI]

Berenice Martínez-Barona

Jérôme Monnot

Peter Mursic

Theor. Comput. Sci., 2021

Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2021

Searching for square-complementary graphs: Complexity of recognition and further nonexistence results.

[BibT_eX]

[DOI]

Ratko Darda

Miguel A. Pizaña

Discret. Math., 2021

Tree decompositions with bounded independence number and their algorithmic applications.

[BibT_eX]

[DOI]

CoRR, 2021

Graphs with at most two moplexes.

[BibT_eX]

[DOI]

CoRR, 2021

Polynomially Bounding the Number of Minimal Separators in Graphs: Reductions, Sufficient Conditions, and a Dichotomy Theorem.

[BibT_eX]

[DOI]

Electron. J. Comb., 2021

Graphs with Two Moplexes.

[BibT_eX]

[DOI]

Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium, 2021

Vertex Cover at Distance on H-Free Graphs.

[BibT_eX]

[DOI]

Mirza Krbezlija

Proceedings of the Combinatorial Algorithms - 32nd International Workshop, 2021

Allocating Indivisible Items with Minimum Dissatisfaction on Preference Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Decision Theory - 7th International Conference, 2021

2020

Non realizable degree sequences of dual graphs on surfaces.

[BibT_eX]

[DOI]

Dataset, May, 2020

Non realizable degree sequences of dual graphs on surfaces.

[BibT_eX]

[DOI]

Dataset, May, 2020

Bipartite graphs of small readability.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1-Sperner hypergraphs.

[BibT_eX]

[DOI]

J. Graph Theory, 2020

Mind the independence gap.

[BibT_eX]

[DOI]

Discret. Math., 2020

On the degree sequences of dual graphs on surfaces.

[BibT_eX]

[DOI]

CoRR, 2020

Treewidth Versus Clique Number in Graph Classes with a Forbidden Structure.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2020

Edge Elimination and Weighted Graph Classes.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2020

Fair Packing of Independent Sets.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 31st International Workshop, 2020

2019

New algorithms for weighted k-domination and total k-domination problems in proper interval graphs.

[BibT_eX]

[DOI]

Valeria Alejandra Leoni

Maria Inés Lopez Pujato

Theor. Comput. Sci., 2019

A dichotomy for weighted efficient dominating sets with bounded degree vertices.

[BibT_eX]

[DOI]

Andreas Brandstädt

Inf. Process. Lett., 2019

A Characterization of Claw-free CIS Graphs and New Results on the Order of CIS Graphs.

[BibT_eX]

[DOI]

Liliana Alcón

Marisa Gutierrez

Proceedings of the tenth Latin and American Algorithms, Graphs and Optimization Symposium, 2019

Detecting strong cliques.

[BibT_eX]

[DOI]

Bernard Ries

Discret. Math., 2019

Decomposing 1-Sperner Hypergraphs.

[BibT_eX]

[DOI]

Electron. J. Comb., 2019

MIPUP: minimum perfect unmixed phylogenies for multi-sampled tumors via branchings and ILP.

[BibT_eX]

[DOI]

Bioinform., 2019

Linear separation of connected dominating sets in graphs.

[BibT_eX]

[DOI]

Ars Math. Contemp., 2019

Minimal Separators in Graph Classes Defined by Small Forbidden Induced Subgraphs.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2019

A Polynomial-Time Algorithm for the Independent Set Problem in P_10, C_4, C_6 -Free Graphs.

[BibT_eX]

[DOI]

Edin Husic

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2019

Avoidable Vertices and Edges in Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

2018

Minimum connected transversals in graphs: New hardness results and tractable cases using the price of connectivity.

[BibT_eX]

[DOI]

Matthew Johnson

Daniël Paulusma

Theor. Comput. Sci., 2018

Complexity and Algorithms for Finding a Perfect Phylogeny from Mixed Tumor Samples.

[BibT_eX]

[DOI]

IEEE ACM Trans. Comput. Biol. Bioinform., 2018

Perfect Phylogenies via Branchings in Acyclic Digraphs and a Generalization of Dilworth's Theorem.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2018

On Almost Well-Covered Graphs of Girth at Least 6.

[BibT_eX]

[DOI]

Discret. Math. Theor. Comput. Sci., 2018

On total domination in the Cartesian product of graphs.

[BibT_eX]

[DOI]

Tim Kos

Discuss. Math. Graph Theory, 2018

Graphs vertex-partitionable into strong cliques.

[BibT_eX]

[DOI]

Bernard Ries

Discret. Math., 2018

1-perfectly orientable K4-minor-free and outerplanar graphs.

[BibT_eX]

[DOI]

Tim Kos

Discret. Appl. Math., 2018

Weighted efficient domination for some classes of H-free and of (H1, H2)-free graphs.

[BibT_eX]

[DOI]

Andreas Brandstädt

Vassilis Giakoumakis

Discret. Appl. Math., 2018

A three-person deterministic graphical game without Nash equilibria.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2018

Domination parameters with number : Interrelations and algorithmic consequences.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2018

Preface: Special Issue on the Ninth International Colloquium on Graphs and Optimization (GO IX), 2014.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2018

Searching for square-complementary graphs: non-existence results and complexity of recognition.

[BibT_eX]

[DOI]

Ratko Darda

Miguel A. Pizaña

CoRR, 2018

New Algorithms for Weighted k-Domination and Total k-Domination Problems in Proper Interval Graphs.

[BibT_eX]

[DOI]

Valeria Alejandra Leoni

Maria Inés Lopez Pujato

CoRR, 2018

Stable Sets in {ISK4, wheel}-Free Graphs.

[BibT_eX]

[DOI]

Irena Penev

Nicolas Trotignon

Algorithmica, 2018

Improved Algorithms for k-Domination and Total k-Domination in Proper Interval Graphs.

[BibT_eX]

[DOI]

Valeria Alejandra Leoni

Maria Inés Lopez Pujato

Proceedings of the Combinatorial Optimization - 5th International Symposium, 2018

2017

Equistarable Graphs and Counterexamples to Three Conjectures on Equistable Graphs.

[BibT_eX]

[DOI]

Nicolas Trotignon

J. Graph Theory, 2017

Partial Characterizations of 1-Perfectly Orientable Graphs.

[BibT_eX]

[DOI]

J. Graph Theory, 2017

Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs.

[BibT_eX]

[DOI]

Didem Gözüpek

Discret. Math. Theor. Comput. Sci., 2017

1-perfectly orientable graphs and graph products.

[BibT_eX]

[DOI]

Discret. Math., 2017

On two extensions of equimatchable graphs.

[BibT_eX]

[DOI]

Zakir Deniz

Tínaz Ekim

Mordechai Shalom

Discret. Optim., 2017

On the complexity of the identifiable subgraph problem, revisited.

[BibT_eX]

[DOI]

Stefan Kratsch

Discret. Appl. Math., 2017

Preface: Algorithmic Graph Theory on the Adriatic Coast.

[BibT_eX]

[DOI]

Pinar Heggernes

Marcin Jakub Kaminski

Discret. Appl. Math., 2017

On equistable, split, CIS, and related classes of graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2017

Almost Well-Covered Graphs Without Short Cycles.

[BibT_eX]

[DOI]

CoRR, 2017

The minimum conflict-free row split problem revisited: a branching formulation and (in)approximability issues.

[BibT_eX]

[DOI]

CoRR, 2017

Minimal dominating sets in lexicographic product graphs.

[BibT_eX]

[DOI]

Didem Gözüpek

CoRR, 2017

The Minimum Conflict-Free Row Split Problem Revisited.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2017

Induced Embeddings into Hamming Graphs.

[BibT_eX]

[DOI]

Peter Mursic

Marcelo Mydlarz

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

2016

On Three Extensions of Equimatchable Graphs.

[BibT_eX]

[DOI]

Zakir Deniz

Tínaz Ekim

Mordechai Shalom

Electron. Notes Discret. Math., 2016

1-perfectly orientable K4-minor-free and outerplanar graphs.

[BibT_eX]

[DOI]

Tim Kos

Electron. Notes Discret. Math., 2016

The price of connectivity for cycle transversals.

[BibT_eX]

[DOI]

Matthew Johnson

Daniël Paulusma

Eur. J. Comb., 2016

Equistarable bipartite graphs.

[BibT_eX]

[DOI]

Discret. Math., 2016

On the readability of overlap digraphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2016

Graph classes with and without powers of bounded clique-width.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2016

Strong cliques and equistability of EPT graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2016

A threshold approach to connected domination.

[BibT_eX]

[DOI]

CoRR, 2016

A three-person chess-like game without Nash equilibria.

[BibT_eX]

[DOI]

CoRR, 2016

2015

On the complexity of the vector connectivity problem.

[BibT_eX]

[DOI]

Romeo Rizzi

Theor. Comput. Sci., 2015

Spread of influence in weighted networks under time and budget constraints.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

Group irregularity strength of connected graphs.

[BibT_eX]

[DOI]

Marcin Anholcer

Sylwia Cichacz

J. Comb. Optim., 2015

Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2015

Vertex-transitive CIS graphs.

[BibT_eX]

[DOI]

Eur. J. Comb., 2015

On the complexity of the identifiable subgraph problem.

[BibT_eX]

[DOI]

Marcin Jakub Kaminski

Discret. Appl. Math., 2015

On a class of graphs between threshold and total domishold graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2015

1-Sperner hypergraphs.

[BibT_eX]

[DOI]

CoRR, 2015

Recognizing k-equistable Graphs in FPT Time.

[BibT_eX]

[DOI]

Eun Jung Kim

Oliver Schaudt

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2015

Finding a Perfect Phylogeny from Mixed Tumor Samples.

[BibT_eX]

[DOI]

Proceedings of the Algorithms in Bioinformatics - 15th International Workshop, 2015

2014

Set graphs. II. Complexity of set graph recognition and similar problems.

[BibT_eX]

[DOI]

Romeo Rizzi

Alexandru I. Tomescu

Theor. Comput. Sci., 2014

Latency-bounded target set selection in social networks.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2014

Vector connectivity in graphs.

[BibT_eX]

[DOI]

Networks, 2014

Graphs Without Large Apples and the Maximum Weight Independent Set Problem.

[BibT_eX]

[DOI]

Christopher Purcell

Graphs Comb., 2014

Graphs whose complement and square are isomorphic.

[BibT_eX]

[DOI]

Discret. Math., 2014

Dominating sequences in graphs.

[BibT_eX]

[DOI]

Discret. Math., 2014

On CIS circulants.

[BibT_eX]

[DOI]

Discret. Math., 2014

Set graphs. IV. Further connections with claw-freeness.

[BibT_eX]

[DOI]

Alexandru I. Tomescu

Discret. Appl. Math., 2014

A characterization of line graphs that are squares of graphs.

[BibT_eX]

[DOI]

Andrea Oversberg

Oliver Schaudt

Discret. Appl. Math., 2014

Equistable simplicial, very well-covered, and line graphs.

[BibT_eX]

[DOI]

Vadim E. Levit

Discret. Appl. Math., 2014

Total domishold graphs: A generalization of threshold graphs, with connections to threshold hypergraphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2014

On the structure of 1-perfectly orientable graphs.

[BibT_eX]

[DOI]

CoRR, 2014

Graphs of Power-Bounded Clique-Width.

[BibT_eX]

[DOI]

CoRR, 2014

How to go Viral: Cheaply and Quickly.

[BibT_eX]

[DOI]

Proceedings of the Fun with Algorithms - 7th International Conference, 2014

2013

Hereditary Efficiently Dominatable Graphs.

[BibT_eX]

[DOI]

J. Graph Theory, 2013

Critical properties of graphs of bounded clique-width.

[BibT_eX]

[DOI]

Discret. Math., 2013

Set graphs. I. Hereditarily finite sets and extensional acyclic orientations.

[BibT_eX]

[DOI]

Alexandru I. Tomescu

Discret. Appl. Math., 2013

Computing square roots of trivially perfect and threshold graphs.

[BibT_eX]

[DOI]

Oliver Schaudt

Discret. Appl. Math., 2013

Resilience and optimization of identifiable bipartite graphs.

[BibT_eX]

[DOI]

Epameinondas Fritzilas

Jérôme Monnot

Yasmín Á. Ríos-Solís

Discret. Appl. Math., 2013

On the approximability and exact algorithms for vector domination and related problems in graphs.

[BibT_eX]

[DOI]

Ugo Vaccaro

Discret. Appl. Math., 2013

A note on domination and independence-domination numbers of graphs.

[BibT_eX]

[DOI]

Ars Math. Contemp., 2013

Linear Separation of Total Dominating Sets in Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2013

New Polynomial Cases of the Weighted Efficient Domination Problem.

[BibT_eX]

[DOI]

Andreas Brandstädt

Ragnar Nevries

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

Induced Subtrees in Interval Graphs.

[BibT_eX]

[DOI]

Pinar Heggernes

Pim van 't Hof

Proceedings of the Combinatorial Algorithms - 24th International Workshop, 2013

2012

Complexity of independent set reconfigurability problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2012

Graphs of separability at most 2.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2012

On the Recognition of k-Equistable Graphs.

[BibT_eX]

[DOI]

Vadim E. Levit

David Tankus

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2012

2011

Shortest paths between shortest paths.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

The plane-width of graphs.

[BibT_eX]

[DOI]

J. Graph Theory, 2011

Equistable graphs, general partition graphs, triangle graphs, and graph products.

[BibT_eX]

[DOI]

Stefko Miklavic

Discret. Appl. Math., 2011

Competitive Boolean function evaluation: Beyond monotonicity, and the symmetric case.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2011

Complexity results for equistable graphs and related classes.

[BibT_eX]

[DOI]

James B. Orlin

Gábor Rudolf

Ann. Oper. Res., 2011

Competitive evaluation of threshold functions in the priced information model.

[BibT_eX]

[DOI]

Ann. Oper. Res., 2011

Hardness, Approximability, and Exact Algorithms for Vector Domination and Total Vector Domination in Graphs.

[BibT_eX]

[DOI]

Ugo Vaccaro

Proceedings of the Fundamentals of Computation Theory - 18th International Symposium, 2011

A hereditary view on efficient domination.

[BibT_eX]

[DOI]

Proceedings of the 10th Cologne-Twente Workshop on graphs and combinatorial optimization. Extended Abstracts, 2011

2010

On the Maximum Independent Set Problem in Subclasses of Planar Graphs.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2010

Structural Identifiability in Low-Rank Matrix Factorization.

[BibT_eX]

[DOI]

Epameinondas Fritzilas

Sven Rahmann

Yasmín Á. Ríos-Solís

Algorithmica, 2010

Shortest Paths between Shortest Paths and Independent Sets.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 21st International Workshop, 2010

Graphs of Separability at Most Two: Structural Characterizations and Their Consequences.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 21st International Workshop, 2010

A Better Bouncer's Algorithm.

[BibT_eX]

[DOI]

Proceedings of the Fun with Algorithms, 5th International Conference, 2010

2009

The Exact Weighted Independent Set Problem in Perfect Graphs and Related Classes.

[BibT_eX]

[DOI]

Jérôme Monnot

Electron. Notes Discret. Math., 2009

Recent developments on graphs of bounded clique-width.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2009

Simple and Fast Reoptimizations for the Steiner Tree Problem.

[BibT_eX]

[DOI]

Bruno Escoffier

Vangelis Th. Paschos

Algorithmic Oper. Res., 2009

2008

A polynomial algorithm to find an independent set of maximum weight in a fork-free graph.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2008

On finding augmenting graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2008

The Maximum Independent Set Problem in Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2008, 2008

Computing with Priced Information: When the Value Makes the Price.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

2007

Tree-Width and Optimization in Bounded Degree Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2007

Maximum independent sets in graphs of low degree.

[BibT_eX]

[DOI]

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

On the maximum independent set problem in subclasses of planar and more general graphs.

[BibT_eX]